#P18215. Strength

Strength

Strength

人们经常用四舍五入来表达近似的数值。例如,一顿饭花费了 98 元,人们可能会说“花了一百元”。如果反复舍入,结果甚至可能与原值相差很大:145 可以先舍入为 150,再舍入为 200。

对于一个非负整数 vv,允许进行如下操作:

  1. 将其十进制表示写作 vkvk−1…v1v_kv_{k-1}\ldots v_1,选择其中一位 i∈{1,2,…,k}i\in\{1,2,\ldots,k\},其中 v1v_1 是个位。
  2. 如果 vi<5v_i<5,将 vv 替换为 v−vi⋅10i−1v-v_i\cdot 10^{i-1};否则,将 vv 替换为 v+(10−vi)⋅10i−1v+(10-v_i)\cdot 10^{i-1}。

每次操作只对选定的数位舍入;向高位产生的进位按通常的十进制加法处理,选定数位右侧的各位保持不变。允许进行任意多次操作,也允许一次都不操作。

给定非负整数 x,zx,z,求有多少个整数 y∈[0,z]y\in[0,z],可以经过上述操作变成 xx。不同的操作顺序即使得到相同结果,也只将同一个初值 yy 计算一次。

输入格式

第一行包含一个整数 TT,表示测试用例数。

接下来 TT 行,每行包含两个整数 x,zx,z。

输出格式

对每个测试用例输出一行,包含一个整数,表示答案。

数据范围

  • 1≤T≤1051\le T\le 10^5;
  • 0≤x,z≤10180\le x,z\le 10^{18}。

样例

5
0 2147483646
10 100
671232353 1232363
123001006660996 3122507962333010
100019990010301090 44519984489341188
2147483647
55
0
1919810
114514

样例说明

第二个测试用例中,所有形如 10i+j10i+j,其中 i∈{0,1,…,9}i\in\{0,1,\ldots,9\}、j∈{5,6,7,8,9}j\in\{5,6,7,8,9\} 的数,以及 10,11,12,13,1410,11,12,13,14,都能变成 1010,因此答案为 5555。