きつねの太郎と次郎はPrime Hazardというコンピューターゲームで遊んでいる。

Prime Hazardに登場するキャラクターには2以上の整数が書かれていて、素数が書かれたキャラクターはプレイヤーの仲間であり、合成数が書かれたキャラクターはプレイヤーの敵である。

プレイヤーはキャラクターに書かれた数字を見て、瞬時に敵か仲間かを判断し敵だけを攻撃しなくてはならない。敵は書かれている数字の最小の素因数を入力することで倒すことができる。

太郎と次郎はこのゲームをプレイする際に次のような役割分担をすることにした。

• 太郎は敵の数字を読んでその情報を次郎に伝える。
• 次郎は太郎からの情報を元に、キャラクターが敵かどうか、敵であれば最小の素因数は何かを判断する。

一度に大量のキャラクターについて処理しなくてはならないため、情報の伝達はできるだけ簡単にしたい。太郎は次郎に0か1の数字をいくつか伝えることにした。

2以上の正整数Nが与えられる。Nが素数か判定せよ。合成数の場合は最小の素因数を求めよ。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ taro(N):
  • N -- 与えられた正整数。
  このプロシージャ中で send(b) を繰り返し呼び出すことで次郎にデータを送信することが可能である。ただし b は 0 または 1 でなければならない。このプロシージャは jiro(S, X) よりも先に1度だけ呼び出され、戻り値を持たない。
• 次のパラメータを持つプロシージャ jiro(S, X):
  • S -- 太郎から送られてきたデータの長さ(ビット数)。
  • X -- S 個の整数からなる1次元配列。0 ≦ i ＜ S に対して X[i] は taro(N) 中で send(b) が i+1 回目に呼び出された際の b の値に等しい。
  このプロシージャは taro(N) が呼び出された後に1度だけ呼び出される。このプロシージャはNが素数である場合は -1, 合成数の場合は最小の素因数を戻り値として返す必要がある。

N = 7

の場合を考える。

taro 中で send が次のように呼び出されたとする。

このとき jiro 呼び出しにおいて S = 4 であり、

となる。

この場合、7 は素数であるので、jiro は -1 を返さなければならない。

N = 6

の場合を考える。

この場合、6 は合成数であり、最小の素因数は 2 であるので、 jiro は 2 を返さなければならない。