D - 183184 Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

正整数 x,y に対して f(x,y) を以下で定義します。

  • 十進表記の x,y をそれぞれ文字列として解釈しこの順に連結して得られる文字列を z とする。z を十進表記の整数として解釈したときの値を f(x,y) とする。

たとえば f(3,14)=314,\ f(100,3)=1003 です。

正の整数 C, D が与えられます。以下を満たす整数 x の個数を求めてください。

  • 1 \leq x \leq D
  • f(C, C+x) は平方数である

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 3 \times 10^5
  • 1 \leq C \leq 2 \times 10^8
  • 1 \leq D \leq 5 \times 10^9
  • 入力される値はすべて整数

入力

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

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

\textrm{case}_i は i 番目のテストケースを表す。各テストケースは以下の形式で与えられる。

C D

出力

T 行出力せよ。i 行目 (1 \leq i \leq T) には i 番目のテストケースに対する答えを出力せよ。

入力例 1

4
4 80
183 5000
18 10
824 5000000000

出力例 1

3
2
0
1421

1 番目のテストケースにおいて、条件を満たす x は x = 5, 37, 80 の 3 通りです。

  • x=5 のとき f(C, C+5) = f(4,9) = 49 = 7^2
  • x=37 のとき f(C, C+37) = f(4,41) = 441 = 21^2
  • x=80 のとき f(C, C+80) = f(4,84) = 484 = 22^2

2 番目のテストケースにおいて、条件を満たす x は x = 1, 3133 の 2 通りです。

  • x=1 のとき f(C, C+1) = f(183,184) = 183184 = 428^2
  • x=3133 のとき f(C, C+3133) = f(183,3316) = 1833316 = 1354^2

3 番目のテストケースにおいて、条件を満たす x は 0 通りです。

4 番目のテストケースにおいて、条件を満たす x は 1421 通りです。

Score : 400 points

Problem Statement

For positive integers x and y, define f(x,y) as follows:

  • Let z be the string obtained by interpreting x,y in decimal notation as strings and concatenating them in this order. Let f(x,y) be the value when z is interpreted as an integer in decimal notation.

For example, f(3,14)=314,\ f(100,3)=1003.

You are given positive integers C and D. Find the number of integers x that satisfy the following conditions:

  • 1 \leq x \leq D
  • f(C, C+x) is a perfect square.

You are given T test cases, find the answer for each of them.

Constraints

  • 1 \leq T \leq 3 \times 10^5
  • 1 \leq C \leq 2 \times 10^8
  • 1 \leq D \leq 5 \times 10^9
  • All input values are integers.

Input

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

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

\textrm{case}_i represents the i-th test case. Each test case is given in the following format:

C D

Output

Output T lines. The i-th line (1 \leq i \leq T) should contain the answer to the i-th test case.

Sample Input 1

4
4 80
183 5000
18 10
824 5000000000

Sample Output 1

3
2
0
1421

For the first test case, there are three values of x that satisfy the conditions: x = 5, 37, 80.

  • When x=5, f(C, C+5) = f(4,9) = 49 = 7^2
  • When x=37, f(C, C+37) = f(4,41) = 441 = 21^2
  • When x=80, f(C, C+80) = f(4,84) = 484 = 22^2

For the second test case, there are two values of x that satisfy the conditions: x = 1, 3133.

  • When x=1, f(C, C+1) = f(183,184) = 183184 = 428^2
  • When x=3133, f(C, C+3133) = f(183,3316) = 1833316 = 1354^2

For the third test case, there are zero values of x that satisfy the conditions.

For the fourth test case, there are 1421 values of x that satisfy the conditions.