問題文

二つの異なる奇素数 $P$ と $Q$ の積である整数 $N$ が与えられるので、$P$ と $Q$ を出力してください。ただし、あなたは量子コンピュータにアクセスして $N$ と互いに素な $N$ 未満の正の整数 $A$ について法 $N$ に関する $A$ の位数をクエリすることができます。

ここで整数 $N\ge 2$ と $N$ と互いに素な正の整数 $A$ について、法 $N$ に関する $A$ の位数とは $A^R \equiv 1 \mod N$ を満たす最小の正の整数 $R$ のことをいいます。

入出力

入力の一行目には

$N$

が与えられます。 $N$ は $2^{1024}$ 未満の正の整数であり、ちょうど二つの異なる奇数の素因数を持つことが保証されています。 $N$ と互いに素な $N$ 未満の正の整数 $A$ をクエリすると、法 $N$ に関する $A$ の位数が入力されます。 質問クエリのフォーマットは

? A

! P Q

サンプル

15
1
4
2
4
4
2
4
2 

? 1
? 2
? 4
? 7
? 8
? 11
? 13
? 14
! 3 5