問題

ahri はちらし寿司が食べたいです。

ところで、条件 x2x(mod10N)x^2 \equiv x \pmod {10^N} を満たす NN 桁の非負整数 xx昇順に全て答えてください。

制約

  • 1N91 \leqq N \leqq 9
  • 入力は整数

入力

NN

出力

条件を満たす非負整数を昇順に改行区切りで全て出力してください。

ただし、そのような整数が存在しないときは 1-1 を出力してください。

サンプル

入力1
1
出力1
1
5
6

1×1=1, 5×5=25, 6×6=361 \times 1 = 1, \ 5 \times 5 = 25, \ 6 \times 6 = 36

11(mod101), 255(mod101), 366(mod101)1 \equiv 1 \pmod {10^1}, \ 25 \equiv 5 \pmod {10^1}, \ 36 \equiv 6 \pmod {10^1}

よって、条件を満たす非負整数は 1, 5, 6 の3個です。

入力2
3
出力2
376
625

376×376=141376, 625×625=390625376 \times 376 = 141376, \ 625 \times 625 = 390625

376, 625 以外に条件を満たす非負整数は存在しません。

入力3
6
出力3
109376
890625

Submit


Go (1.21)