Qizz Quzz (Easy)

Generalized Fizz Buzz works like the original Fizz Buzz. The program prints positive integers starting from 1, but some special numbers and their multiples are replaced by strings. If a number is divisible by several special numbers, it is replaced by the concatenation of all their strings.

Your task is not to implement Generalized Fizz Buzz. You are given a sequence and must decide whether it can be the output of a Generalized Fizz Buzz program.

A particular instance is defined by these parameters: a positive integer $n$, a nonnegative integer $k$, distinct positive integers $d_1, d_2, ..., d_k$ with $d_1 < d_2 < ... < d_k$, and strings $s_1, ..., s_k$ of lowercase English letters.

The number $n$ is the length of the output sequence. The number $k$ is the number of replacement rules. Each rule says: instead of multiples of $d_i$, print $s_i$. If several rules apply, the label is the concatenation of the matching $s_i$, ordered from the smallest to the largest divisor.

For example, the original Fizz Buzz has $k = 2$, $d = (3, 5)$, and $s = (fizz, buzz)$. For $n = 17$ the output is 1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17. Instead of 15, the program prints fizzbuzz because 15 is divisible by both 3 and 5. The label cannot be buzzfizz, because the order of the $s_i$ cannot change.

Samko wrote his own implementation. It handles only inputs where $k \le 2$ and every string $s_i$ has length exactly 4.

Samko showed you a sequence of labels $\ell_1, ..., \ell_n$. Find the largest $q$ such that the prefix $\ell_1, ..., \ell_q$ can be the output of Samko's program.

The first line contains an integer $t$, the number of test cases. Each test case is preceded by a blank line. Each test case has two lines. The first line contains a positive integer $n \le 1000$, the number of labels. The second line contains $n$ non-empty tokens $\ell_1, ..., \ell_n$ separated by single spaces. Each token contains only digits and lowercase English letters.

For each test case, output one line with the integer $q$.

In the first example, the first six tokens are the output of a Generalized Fizz Buzz program with $k = 1$, $d_1 = 1$, and $s_1 = mlem$. Both Samko's and Monika's programs can handle this input, so the answer is 6 for each. In the second example, 2 must be replaced with qizz and 3 with quzz. The first five tokens match that sequence. The next token should be qizzquzz instead of quzzqizz, and the last one should be 7 instead of 007. In the third example, hunter2 is wrong because it contains both letters and digits. In the fourth example, $d = (1, 2)$ and $s = (haha, haha)$. The strings $s_i$ do not have to be distinct. In the fifth example, bat is already wrong because Samko's program cannot handle a string of length 3.