周期はトーティエント関数で計算できます．
大きくなる場合は，周期に突入してるので，pw(hoge) mod 周期 + 周期ぐらいを愚直に計算していけば良い．
大きくならない可能性がある場合は場合分けで弾きました．