003 - FizzBuzz Game Organization

問題

あなたはFizzBuzz Game Organization(以下FGO)に所属しています。

FGOには$10^{1000000007}$人が所属しており、その中の何人かで毎日FizzBuzzをしています。

FizzBuzzの遊び方を説明します。プレイヤーは円状に座り、最初のプレイヤーは「1」と数字を発言します。次のプレイヤーは直前のプレイヤーの次の数字に1を足した数字を発言していきます。ただし、数字が3の倍数である場合は"Fizz"、5での倍数である場合は"Buzz"、15の倍数である場合は"FizzBuzz"を数の代わりに発言しなければなりません。発言を間違えた者や、ためらった者は脱落となるというゲームです。

あなたは過去のFizzBuzzで自分がなんと発言したか記録をとっているのですが、あなたは数字をかけないので数字は一律に"N"一文字に置換して記録しました。加えてゲームが6周目に入ると熱中してしまって記録をわすれてしまいます。なので、記録は1回のゲームにつき5つしかありません。

例えば2人のプレイではあなたは1番めなので、本来の記録は {1, "Fizz", "Buzz", 7, "Fizz"} ですが、数字がかけないあなたの記録は {"N", "Fizz", "Buzz", "N", "Fizz"} となっています。

あなたはゲームの参加人数が$N$人のとき、絶対に$floor((N+1)/2)$番目でゲームに参加していました。

過去$Q$件の記録それぞれの参加人数の調査をします。しかし、この記録では参加人数は一意に定まりません。少なくとも何人参加していたのか調べてください。

入力

1行目に記録の数$Q$が与えられ、以降以下のフォーマットで入力が与えられる。

$Record_1$ $Record_2$ $Record_3$ $Record_4$ $Record_5$

各行に文字列が5つ与えられる。文字列は"N", "Fizz", "Buzz", "FizzBuzz"のいずれかである。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq Q \leq 10^{5}$
• 人数の推定が可能な記録のみ与えられる

入出力例

入力例1

1
N Fizz Buzz N Fizz

出力例1

2

この記録は$N=2$のときに得られる。他に596人で行ったときも同様の結果は得られるが、最低人数を出力する。

入力例2

5
N Buzz N N N
FizzBuzz FizzBuzz FizzBuzz FizzBuzz FizzBuzz 
N N Fizz N Buzz
Fizz N N Fizz N
Buzz N N N N

出力例2

3
30
1
5
9