只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
4703 - 幸运数
你应该知道，什么是最大公约数：对于任意两个非零整数x，y，若整数d能同时被x和y整除，则称d为x与y的公约数 。定义x与y的最大公约数gcd(x, y)为x与y的最大的公约数。如gcd(6, 9) = 3，gcd(12, 16) = 4，gcd(25, 32) = 1，等等。这里，我们定义什么是幸运数：对于一个正整数d，我们使用di表示d在十进制表示下，按从低位到高位 顺序的第i位数字。设F(d)表示d的奇数位的数字之和，即F(d) = d1 + d3 + d5 + ……；设G(d)表示d的偶数位的 数字之和，即G(d) = d2 + d4 + d6 + ……；若F(d)与G(d)均大于0，且F(d)与G(d)的最大公约数不超过K，则称d 为幸运数。其中K是一个已知的常数。举个例子来说，若d = 641，则d1 = 1，d2 = 4，d3 = 6，F(641) = 1 + 6 = 7，G(641) = 4。此时F(d)与G(d)的最大公约数即gcd(7, 4)等于1。则当K不小于1时641是幸运数。请你回答下面 的问题：对于给定的K，在不小于L并且不超过R的所有整数中，有多少个数是幸运数？注意，输入文件包含多组测 试数据。
输入
第一行包含一个整数T，表示有T组测试数据。 接下来T行，每行包含三个整数K、L、R，表示一次询问。
输出
输出T行，每行一个整数，依次表示每组测试数据的答案。 1 ≤ L ≤ R ≤ 10^18， 1 ≤ K ≤ 10^2，1 ≤ T ≤ 1000
样例
输入
5 1 1 10 2 28 34 100 987654321 987654321 1 1 50000 1 50001 100000
输出
0 5 1 30298 30309 【样例解释】 K = 1时，1到10之间不存在幸运数。 K = 2时，28到34之间的幸运数有28、29、31、32、34，共5个。 K = 100时，987654321是幸运数。 K = 1时，1到50000之间的幸运数有30298个，50001到100000之间的幸运数有30309个。