AtCoder Regular Contest 057

C - 2乗根


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 262.144MB

問題文

\sqrt{N} の上 k 桁が a_1a_2...a_k となるような最小の正整数 N を求めてください。

ただし、\sqrt{N} の上 k 桁とは、\sqrt{N} の十進表記を、先頭につづく 0 と小数点を除いて上から読んだときの k 番目の数字までを並べた列を指します。 例えば、\sqrt{2} の上 5 桁は 14142\sqrt{100} の上 6 桁は 100000 です。


制約

  • 1 ≦ k ≦ 1000
  • a_1 ≠ 0

入力

入力は以下の形式で標準入力から与えられる。

a_1a_2...a_k

出力

\sqrt{N} の上 k 桁が a_1a_2...a_k となるような最小の正整数 N1 行に出力せよ。


入力例1

1414

出力例1

2

入力例2

316

出力例2

10

入力例3

31415926535897932384626433

出力例3

9869604401089358618834491

Submit提出する