Internet Problem Solving Contest

• Easy input data set – Q1
• Hard input data set – Q2

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.

Generalized Fizz Buzz

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₁, …, d_k such that d₁ < d₂ < ⋯ < d_k.
• Strings s₁, …, 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₁ (fizz) and s₂ (buzz) because 15 is divisible both by d₁ (3) and by d₂ (5). Also note that you cannot print buzzfizz for 15 because you cannot change the order of the s_i when concatenating them.

Subproblem Q1

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 ℓ₁, …, ℓ_n. Find the largest q such that the prefix ℓ₁, …, ℓ_q can be the output of Samko’s program.

Subproblem Q2

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 ℓ₁, …, ℓ_n. Find the largest q such that the prefix ℓ₁, …, ℓ_q can be the output of Monika’s program.

Input specification

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 ℓ₁, …, ℓ_n separated by single spaces. Each token will only contain digits and lowercase English letters.

Output specification

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.

Example

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, 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.