Amoeba is a good friend of Xiaoqiang.

In Xiaoqiang's eyes, Amoeba is a literary youth with high grades in composition. To learn the secret of writing good essays, Xiaoqiang asks Amoeba for advice. Amoeba shows Xiaoqiang several essays, and Xiaoqiang feels that these articles seem strangely familiar, as if they were pieced together from some model essays. Xiaoqiang cannot help but cast a suspicious glance at Amoeba, only to find Amoeba wearing a sly smile.

To convincingly demonstrate to Amoeba how "familiar" his essays feel, Xiaoqiang comes up with a quantitative metric for the "degree of familiarity" of an essay: $L_0$.

Xiaoqiang first converts the essay into a binary string (a string of 0s and 1s).

Afterward, Xiaoqiang collects articles from various famous authors, converts them into binary strings as well, and organizes them into a "standard essay library" containing $M$ binary strings.

Xiaoqiang believes that if a binary string has a length of at least $L$ and has appeared in one of the strings in the standard essay library (i.e., it is a contiguous substring of one of the strings in the standard essay library), then it is "familiar." For an essay (a binary string) $A$, if it is possible to partition $A$ into several segments such that the sum of the lengths of the "familiar" segments is at least 90% of the total length of $A$, then $A$ is called a "familiar article." $L_0$ is the maximum value of all $L$ that allow $A$ to be a "familiar article" (if no such $L$ exists, then $L_0 = 0$).

For example: Xiaoqiang's essay library contains the following 2 strings: 10110 000001110

There is an essay to be examined: 1011001100

Xiaoqiang calculates that the maximum value of $L$ for this essay is 4, because the essay to be examined can be viewed as '10110'+'0110'+'0', where '10110' and '0110' are judged to be "familiar." However, when $L = 5$ or greater, there is no partition method that satisfies the condition. Therefore, the $L_0$ for this essay is 4.

Xiaoqiang believes that the $L_0$ value of Amoeba's essay is significantly larger than that of other students. Please help him verify this.

Input

The first line contains two integers $N$ and $M$, representing the number of essays to be checked and the number of lines in Xiaoqiang's standard essay library, respectively.

The next $M$ lines contain binary strings, representing the standard essay library.

The next $N$ lines contain binary strings, representing the $N$ essays.

Output

The output contains $N$ lines, each containing an integer representing the $L_0$ value for that essay.

Examples

Input 1

1 2
10110
000001110
1011001100

Output 1

4

Note 1

This is the example from the problem description.

Constraints

For 30% of the test data, the length of the input file does not exceed 1000 bytes. For 50% of the test data, the length of the input file does not exceed 61000 bytes. For 80% of the test data, the length of the input file does not exceed 250000 bytes. For 100% of the test data, the length of the input file does not exceed 1100000 bytes.