問題文

$3$以上の素数$p$と，$x \equiv 1 \mathbf{mod}p$を満たす正整数$x$と，正整数$n$が与えられます．

$(x^n-1)$が$p$で何回割り切ることができるか求めてください．

制約

• $3 \leq p \leq 30$
• $p$は素数である．
• $1 \leq x \leq 60$
• $1 \leq n \leq 10$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます．

出力

答えを$1$行に出力せよ．

サンプル

3 10 9

4

$10^9-1=999999999=3^4 \times 37 \times 333667$です．よって$3$で$4$回割り切ることができるので$4$を出力します．

29 59 10

1