Problem L: The Return of FizzBuzz

ICPC World Finals 7日目

いよいよ明日はICPC World Finalsの本番である。 ティー氏はあるオンラインジャッジ(Aru Online Judge)で練習をすることにした。 問題一覧を眺めているとFizzBuzzという問題が目についた。 この問題は、FizzBuzzゲームで得られる発言のn文字目から20文字を出力するというものだ。

…ふぅ。あっという間に解けてしまった。 これでは簡単すぎた。 入力と出力を逆にした問題を作ってみることにしよう。

問題

FizzBuzzとは、1以上の整数を順に、以下のルールに従って発言していくゲームである。

ゲームの進行状況を以下に示す。

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, …

得られた発言を結合することで得られる（無限長の）文字列をFizzBuzz Stringと呼ぶ。 ある文字列\(s\)が与えられる。 \(s\)がFizzBuzz Stringの部分文字列として出現するかを判定し、 出現する場合には最初に出現するインデックスを求めよ。

入力

n
s1
s2
…
sn

入力は複数のテストケースからなる。 1行目にテストケース数\(n\)が与えられる。 2行目から\( n+1 \)行目は各テストケースに対応し、 文字列\( s_{i} \)が1行で与えられる。

出力

\(i\)番目の文字列\( s_{i} \)について、 \( s_{i} \)がFizzBuzz Stringの部分文字列として出現する場合には最初に出現するインデックスを(1-indexで)、 出現しない場合には"-1"を\(i\)行目に出力せよ。

制約

入出力例

入力1

6
78Fizz
98FizzBuzz101
FizzBu
izzFiz
111111111111111
123456789

出力1

16
304
18
-1
7703703700
7795884765

入力例は6つのテストケースからなる。 それぞれ以下の発言に対応する。