AT_arc174_d [ARC174D] Digit vs Square Root

[problemUrl]: https://atcoder.jp/contests/arc174/tasks/arc174_d $ T $ 個のテストケースについて、以下の問題に答えてください。 整数 $ N $ が与えられるので、以下の条件を全て満たす整数 $ x $ の個数を求めてください。 - $ 1\ \le\ x\ \le\ N $ - $ y\ =\ \lfloor\ \sqrt{x}\ \rfloor $ とする。このとき、 $ x,y $ 双方を (先頭に $ 0 $ を含まずに) 十進法で書き下した場合、 $ y $ が $ x $ の接頭辞になる。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ N_1 $ $ N_2 $ $ \vdots $ $ N_T $ 但し、 $ N_i $ は $ i $ 個目のテストケースにおける整数 $ N $ を表す。

全体で $ T $ 行出力せよ。 そのうち $ i $ 行目には、 $ i $ 個目のテストケースに対する答えを整数として出力せよ。

### 制約 - $ T $ は $ 1\ \le\ T\ \le\ 10^5 $ を満たす整数 - $ N $ は $ 1\ \le\ N\ \le\ 10^{18} $ を満たす整数 ### Sample Explanation 1 この入力には、 $ 2 $ 個のテストケースが含まれます。 - $ 1 $ つ目のテストケースについて、 $ x=1 $ は $ y\ =\ \lfloor\ \sqrt{1}\ \rfloor\ =\ 1 $ となり問題文中の条件を満たします。 - $ 2 $ つ目のテストケースについて、例えば $ x=100 $ は $ y\ =\ \lfloor\ \sqrt{100}\ \rfloor\ =\ 10 $ となり問題文中の条件を満たします。