27639번 - Qizz Quzz (Hard) 다국어

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₁, …, 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 = (fizz, 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.

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.

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.

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

• In the first example, the first six tokens are the output of a Generalized Fizz Buzz program for k = 1, d₁ = 1, and s₁ = 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 = (haha, haha). Note that the strings s_i do not have to be distinct.
• In the fifth example, 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.