D - Digit vs Square Root Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

T 個のテストケースについて、以下の問題に答えてください。

整数 N が与えられるので、以下の条件を全て満たす整数 x の個数を求めてください。

  • 1 \le x \le N
  • y = \lfloor \sqrt{x} \rfloor とする。このとき、 x,y 双方を (先頭に 0 を含まずに) 十進法で書き下した場合、 y が x の接頭辞になる。

制約

  • T は 1 \le T \le 10^5 を満たす整数
  • N は 1 \le N \le 10^{18} を満たす整数

入力

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

T
N_1
N_2
\vdots
N_T

但し、 N_i は i 個目のテストケースにおける整数 N を表す。

出力

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

入力例 1

2
1
174

出力例 1

1
22

この入力には、 2 個のテストケースが含まれます。

  • 1 つ目のテストケースについて、 x=1 は y = \lfloor \sqrt{1} \rfloor = 1 となり問題文中の条件を満たします。
  • 2 つ目のテストケースについて、例えば x=100 は y = \lfloor \sqrt{100} \rfloor = 10 となり問題文中の条件を満たします。

Score: 500 points

Problem Statement

Solve the following problem for T test cases.

Given an integer N, find the number of integers x that satisfy all of the following conditions:

  • 1 \le x \le N
  • Let y = \lfloor \sqrt{x} \rfloor. When x and y are written in decimal notation (without leading zeros), y is a prefix of x.

Constraints

  • T is an integer such that 1 \le T \le 10^5.
  • N is an integer such that 1 \le N \le 10^{18}.

Input

The input is given from Standard Input in the following format:

T
N_1
N_2
\vdots
N_T

Here, N_i represents the integer N for the i-th test case.

Output

Print T lines in total. The i-th line should contain the answer for the i-th test case as an integer.

Sample Input 1

2
1
174

Sample Output 1

1
22

This input contains two test cases.

  • For the first test case, x=1 satisfies the conditions since y = \lfloor \sqrt{1} \rfloor = 1.
  • For the second test case, for example, x=100 satisfies the conditions since y = \lfloor \sqrt{100} \rfloor = 10.