After a successful presentation of your coding skills on the Fizz Buzz problem you have advanced to the second round of interviews for your dream job of code ninja at FizzBuzz Corp. In this interview you will tackle the Generalized Fizz Buzz problem.

Generalized Fizz Buzz is similar to the original Fizz Buzz. The program must print positive integers starting from 1, but some special numbers (and their multiples) should be replaced by strings. If something is divisible by multiple special numbers, it must be replaced by a concatenation of all their strings.

In this problem, your task **isn’t** to implement Generalized Fizz Buzz. Instead, you will be given a sequence and you need to decide whether it can be the output of a Generalized Fizz Buzz program.

A particular instance of Generalized Fizz Buzz is defined by the following parameters:

- A positive integer
*n*. - A nonnegative integer
*k*. - Distinct positive integers
*d*_{1}, …,*d*_{k}such that*d*_{1}<*d*_{2}< ⋯ <*d*_{k}. - Strings
*s*_{1}, …,*s*_{k}of lowercase English letters.

Their meaning is as follows:

- The number
*n*is the length of the sequence the program should output. - The number
*k*is the number of replacement rules. - Each of the replacement rules has the form “Instead of multiples of
*d*_{i}print the string*s*_{i}.” - If multiple replacement rules apply, the label that should be printed is obtained by concatenating all the corresponding
*s*_{i}, ordered**from the smallest to the largest divisor**.

For example, the original Fizz Buzz corresponds to *k* = 2, *d* = (3, 5), and $s=({\tt fizz},{\tt buzz})$. The correct output of that program for *n* = 17 would be:

`1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17`

Note that instead of 15 we printed the concatenation of *s*_{1} (`fizz`

) and *s*_{2} (`buzz`

) because 15 is divisible both by *d*_{1} (3) and by *d*_{2} (5). Also note that you cannot print `buzzfizz`

for 15 because you cannot change the order of the *s*_{i} when concatenating them.

Samko has written his own implementation of a Generalized Fizz Buzz program. However, Samko’s implementation has some additional constraints: It can only handle inputs where *k* ≤ 2 and each of the strings *s*_{i} has length exactly 4.

Samko has shown you a sequence of labels ℓ_{1}, …, ℓ_{n}. Find the largest *q* such that the prefix ℓ_{1}, …, ℓ_{q} can be the output of Samko’s program.

Monika has also written her own implementation of a Generalized Fizz Buzz program. Monika’s program can only handle inputs where each of the strings *s*_{i} has between 1 and 25 characters, inclusive. (Her program can handle arbitrarily large values of *k* and *d*_{i}.)

Monika has shown you a sequence of labels ℓ_{1}, …, ℓ_{n}. Find the largest *q* such that the prefix ℓ_{1}, …, ℓ_{q} can be the output of Monika’s program.

The first line of the input file contains an integer *t* specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of two lines. The first line contains a positive integer *n* ≤ 1000: the number of labels in the sequence you were given. The second line contains the sequence: *n* non-empty tokens ℓ_{1}, …, ℓ_{n} separated by single spaces. Each token will only contain digits and lowercase English letters.

For each test case output one line with the corresponding integer *q*.

Make sure that in **subproblem Q1** the *q* you output corresponds to Samko’s program, while in **subproblem Q2** your output should correspond to Monika’s program.

**Input:**

```
5
7
mlem mlem mlem mlem mlem mlem fail
7
1 qizz quzz qizz 5 quzzqizz 007
8
1 2 3 4 hunter2 is my password
2
haha hahahaha
9
1 bat 3 batman robin batbat 7 batmanman 9
```

**Output for Q1:**

```
6
5
4
2
1
```

**Output for Q2:**

```
6
5
4
2
9
```

- In the first example, the first six tokens are the output of a Generalized Fizz Buzz program for
*k*= 1,*d*_{1}= 1, and $s_1={\tt mlem}$. Both Samko’s and Monika’s program can handle this input, so for each of them the answer is 6. - In the second example, it’s clear that 2 must be replaced with
`qizz`

and 3 with`quzz`

. The first five tokens match that sequence, but the next one 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 numbers. - In the fourth example,
*d*= (1, 2) and $s=({\tt haha},{\tt haha})$. Note that the strings*s*_{i}do not have to be distinct. - In the fifth example,
`bat`

is already wrong in Q1 because Samko’s program cannot handle a three-character string. In Q2 the whole sequence is correct because it’s possible that 2 was replaced by`bat`

, 4 was replaced by`man`

, 5 by`robin`

, 6 also by`bat`

, and 8 also by`man`

.