問題
あなたは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