Qizz Quzz (쉬움)

Generalized Fizz Buzz는 원래의 Fizz Buzz와 같은 방식으로 동작한다. 프로그램은 1부터 양의 정수를 차례로 출력하되, 일부 특수한 수와 그 배수는 문자열로 바꾼다. 어떤 수가 여러 특수한 수로 나누어떨어지면 해당 문자열을 모두 이어 붙인 것으로 바꾼다.

이 문제에서는 Generalized Fizz Buzz를 구현하지 않는다. 주어진 수열이 Generalized Fizz Buzz 프로그램의 출력이 될 수 있는지 판단한다.

하나의 프로그램은 양의 정수 $n$, 음이 아닌 정수 $k$, 서로 다른 양의 정수 $d_1, d_2, ..., d_k$ ($d_1 < d_2 < ... < d_k$), 소문자 영문자로 이루어진 문자열 $s_1, ..., s_k$로 정해진다.

$n$은 출력 수열의 길이이다. $k$는 치환 규칙의 개수이다. 각 규칙은 $d_i$의 배수 대신 $s_i$를 출력한다는 뜻이다. 여러 규칙이 적용되면 해당하는 $s_i$를 $d_i$가 작은 순서부터 이어 붙인 것이 레이블이 된다.

예를 들어 원래의 Fizz Buzz는 $k = 2$, $d = (3, 5)$, $s = (fizz, buzz)$이다. $n = 17$이면 출력은 1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17이다. 15는 3과 5로 모두 나누어떨어지므로 fizzbuzz를 출력한다. $s_i$의 순서는 바꿀 수 없으므로 buzzfizz는 나올 수 없다.

Samko는 자신만의 구현을 작성했다. 이 구현은 $k \le 2$이고 모든 문자열 $s_i$의 길이가 정확히 4인 입력만 처리한다.

Samko가 레이블 수열 $\ell_1, ..., \ell_n$을 보여주었다. Samko의 프로그램이 출력할 수 있는 접두사 $\ell_1, ..., \ell_q$에서 가장 큰 $q$를 구하라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 레이블의 개수인 양의 정수 $n \le 1000$이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 비어 있지 않은 토큰 $n$개 $\ell_1, ..., \ell_n$이 주어진다. 각 토큰은 숫자와 소문자 영문자만 포함한다.

각 테스트 케이스마다 정수 $q$를 한 줄에 출력한다.

첫 번째 예시에서 처음 여섯 토큰은 $k = 1$, $d_1 = 1$, $s_1 = mlem$인 Generalized Fizz Buzz 프로그램의 출력이다. Samko의 프로그램과 Monika의 프로그램 모두 이 입력을 처리할 수 있으므로 두 답은 모두 6이다. 두 번째 예시에서 2는 qizz로, 3은 quzz로 바꿔야 한다. 처음 다섯 토큰은 이 수열과 일치한다. 다음 토큰은 quzzqizz가 아니라 qizzquzz여야 하고, 마지막 토큰은 007이 아니라 7이어야 한다. 세 번째 예시에서 hunter2는 문자와 숫자를 함께 포함하므로 잘못되었다. 네 번째 예시에서 $d = (1, 2)$, $s = (haha, haha)$이다. 문자열 $s_i$가 서로 달라야 할 필요는 없다. 다섯 번째 예시에서 bat는 길이가 3인 문자열이므로 Samko의 프로그램이 처리하지 못해 이미 잘못되었다.