AliceとBobが各ターンでどう操作しても，ゲーム終了後，場にある数は，NNNを素因数分解した結果になり，この状態が負けです．
また，各ターンにおいてどのような操作をしても，場にある数の数はちょうど111つ増えます．
よって，NNNの素因数の数の偶奇により勝敗が決まります．
偶数のときはAliceが勝ち，奇数のときはBobが勝ちます．
以上の解法により，O(n)\mathrm{O(\sqrt n)}O(n)（メジャーな素因数分解法の計算量）で答えを求めることができます．
