Qizz Quzz (어려움)

Fizz Buzz 문제에서 코딩 실력을 보여준 뒤, FizzBuzz Corp.의 코드 닌자 직무 면접 2차 전형에 올랐습니다. 이번 면접에서는 Generalized Fizz Buzz 문제를 풉니다.

Generalized Fizz Buzz는 원래의 Fizz Buzz와 비슷합니다. 프로그램은 1부터 양의 정수를 차례로 출력하되, 일부 특별한 수와 그 배수는 문자열로 바꿔 출력합니다. 어떤 수가 여러 특별한 수로 나누어떨어지면, 해당하는 문자열을 모두 이어 붙인 값으로 바꿉니다.

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

하나의 경우는 다음 매개변수로 정해집니다.

• 양의 정수 $n$.
• 0 이상의 정수 $k$.
• 서로 다른 양의 정수 $d_1 < d_2 < ... < d_k$.
• 소문자 영문자로 이루어진 문자열 $s_1, ..., s_k$.

각 값의 의미는 다음과 같습니다.

• $n$은 프로그램이 출력해야 하는 수열의 길이입니다.
• $k$는 치환 규칙의 개수입니다.
• 각 규칙은 "$d_i$의 배수 대신 문자열 $s_i$를 출력한다"는 형태입니다.
• 여러 규칙이 적용되면, 해당하는 $s_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로 모두 나누어떨어지므로 $s_1$과 $s_2$를 이어 붙인 문자열로 출력합니다. $s_i$의 순서는 바꿀 수 없으므로 15에 buzzfizz를 출력할 수는 없습니다.

Monika도 자신만의 Generalized Fizz Buzz 프로그램을 작성했습니다. 이 프로그램은 각 문자열 $s_i$의 길이가 1자 이상 25자 이하인 입력만 처리합니다. $k$와 $d_i$는 아무리 커도 처리할 수 있습니다.

Monika는 라벨 수열 $\ell_1, ..., \ell_n$을 보여주었습니다. Monika의 프로그램 출력일 수 있는 접두 수열 $\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$들이 서로 달라야 할 필요는 없습니다.
• 다섯 번째 예시에서는 2가 bat, 4가 man, 5가 robin, 6도 bat, 8도 man으로 바뀌었을 수 있으므로 수열 전체가 올바릅니다.