#P4703. 幸运数

幸运数

题目描述

你应该知道,什么是最大公约数:对于任意两个非零整数 x,yx,y,若整数 dd 能同时被 xx 和 yy 整除,则称 dd 为 xx 与 yy 的公约数。定义 xx 与 yy 的最大公约数 gcd⁡(x,y)\gcd(x, y) 为 xx 与 yy 的最大的公约数。如 gcd⁡(6,9)=3\gcd(6, 9) = 3,gcd⁡(12,16)=4\gcd(12, 16) = 4,gcd⁡(25,32)=1\gcd(25, 32) = 1,等等。这里,我们定义什么是幸运数:对于一个正整数 dd,我们使用 did_i 表示 dd 在十进制表示下,按从低位到高位顺序的第 ii 位数字。设 F(d)F(d) 表示 dd 的奇数位的数字之和,即 F(d)=d1+d3+d5+⋯F(d) = d_1 + d_3 + d_5 + \cdots;设 G(d)G(d) 表示 dd 的偶数位的数字之和,即 G(d)=d2+d4+d6+⋯G(d) = d_2 + d_4 + d_6 + \cdots;若 F(d)F(d) 与 G(d)G(d) 均大于 00,且 F(d)F(d) 与 G(d)G(d) 的最大公约数不超过 kk,则称 dd 为幸运数。其中 kk 是一个已知的常数。举个例子来说,若 d=641d = 641,则 d1=1d_1 = 1,d2=4d_2 = 4,d3=6d_3 = 6,F(641)=1+6=7F(641) = 1 + 6 = 7,G(641)=4G(641) = 4。此时 F(d)F(d) 与 G(d)G(d) 的最大公约数即 gcd⁡(7,4)\gcd(7, 4) 等于 11。则当 kk 不小于 11 时 641641 是幸运数。请你回答下面的问题:对于给定的 kk,在不小于 LL 并且不超过 RR 的所有整数中,有多少个数是幸运数?注意,输入文件包含多组测试数据。

输入格式

第一行包含一个整数 TT,表示有 TT 组测试数据。 接下来 TT 行,每行包含三个整数 k,l,rk,l,r,表示一次询问。

输出格式

输出 TT 行,每行一个整数,依次表示每组测试数据的答案。

样例输入

5
1 1 10
2 28 34
100 987654321 987654321
1 1 50000
1 50001 100000

样例输出

0
5
1
30298
30309

样例解释

k=1k = 1 时,11 到 1010 之间不存在幸运数。

k=2k = 2 时,2828 到 3434 之间的幸运数有 2828、2929、3131、3232、3434,共 55 个。

k=100k = 100 时,987654321987654321 是幸运数。

k=1k = 1 时,11 到 5000050000 之间的幸运数有 3029830298 个,5000150001 到 100000100000 之间的幸运数有 3030930309 个。

数据范围与约定

对于 100%100\% 的数据,1≤L≤R≤10181 \le L \le R \le 10^{18}, 1≤k≤1021 \le k\le 10^2,1≤T≤1031 \le T \le 10^3。