← 返回题目列表

AtCoder · abc428_d

G. 十八万三千一百八十四

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

对于正整数 x 和 y,定义 f(x,y) 如下:

  • 让 z 为解释得到的字符串 x,y 以十进制表示为字符串,并按此顺序连接它们。让 f(x,y) 是当 z 被解释为十进制整数。

例如, 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

对于第一个测试用例,有三个值 x 满足条件: x = 5, 37, 80.

  • 当 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

对于第二个测试用例,有两个值 x 满足条件: x = 1, 3133.

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

对于第三个测试用例, x 满足条件。

对于第四个测试用例,有 1421 的值 x 满足条件。