AさんとBさんがある正の整数 を使ってゲームをします。
Aさんから、交互に以下の操作を繰り返します。操作が行えなくなった方の負けです。
・ を割り切れる素数を重複なしに つ以上選び、 をそれらで割ったものに置き換える。
AさんとBさんが共に最善を尽くす時、どちらが勝つでしょうか。
個のテストケースが与えられるので、全てに答えてください。
一行目にテストケースの数 が与えられる。
二行目以降、整数 が一行毎に、 行与えられる。
AさんとBさんが共に最善を尽くした時、どちらが勝つか、答えてください。
Aさんが勝つなら First
を、Bさんが勝つなら Second
を、それぞれのテストケースで改行して出力してください。
4 2 18 100 314159265
First First Second First
1つ目のテストケースは、 です。Aさんが を選ぶことで、 にでき、Bさんが操作を行えないので、Aさんの勝ちです。
2つ目のテストケースは、 です。Aさんがまず を選びます。そうすると、Bさんには で回ってきます。Bさんは しか選べず、次のAさんのターンで を選ぶことで、 にでき、Aさんが勝ちます。