问题 D: 神の数

问题 D: 神の数

时间限制: 1 Sec  内存限制: 128 MB
提交: 316  解决: 69
[状态] [讨论版] [提交] [命题人:]
题目描述

有一天,有一个小朋友送给萌萌的韬韬一本书,书的名字叫做《数》,韬韬对于数字有着无比的狂热,一拿到这本书就沉迷于数的世界无法自拔,不久韬韬看到一个数字被称为神の数字——36,觉得很好奇,从未听说过,又继续往下看,发现原来36好厉害呢,有好多神奇的性质。

   36 = (1 + 3 + 5 +7) + (2 + 4 + 6 + 8) 是前4个奇数与前4个偶数的和

   36 = 1^3+2^3+3^3 还是前3个自然数的立方和

   《三十六计》是一个神奇的东西,可以解决好多神奇的问题,是杰出的军事家孙子大大写就的一篇传世巨擘。

   人体能承受的安全电压是36V,好巧耶。

   … …

   韬韬看到了这么多36的神奇性质,想到了一个问题,给定区间范围[l, r]内有多少跟36相关的数呢,韬韬在想什么样的数是和36相关的呢,换句话说,韬韬在思考如何给“36相关的数”一个定义。

   一个“36相关的数”,首先它的十进制表示中必须得有36吧,嘛,相关度还得够,一定不能有单个的3或者6,单个的3或6不是真的36呀。36036是一个“36相关的数”,而36633不是呢。好像漏掉了什么东西,“这还不够”,韬韬说道。

   一个“36相关的数”,它必须能被36整除,这才是真的和36相关嘛,韬韬发现在[1, 36]区间中只有36这个数满足这些要求。韬韬想知道第二个这样的数是多少呢,很遗憾,貌似100以内找不到这样的数了呢。

   韬韬非常沮丧,他热切地想知道区间[l, r]中“36相关的数”有多少。好像又漏掉了点什么呢,韬韬还想知道[l, r]区间中这些36相关数中有多少“36”存在,毕竟是36嘛。

   既然韬韬现在很沮丧,一点算数的心情都没有了,但是他很想知道上面提到的这些数呢,亲爱的小伙伴你可以帮帮他嘛?

输入

第一行是测试样例数 t (1 <= t <= 10^5) 接下来t行每行包括两个正整数 l, r (1  <=  l <=  r  <=  10^5).

输出

输出包括t行,每行对应一次询问,每行包括2个数 — 区间[l, r]中36相关数的数量, 36相关数中“36”的数量。

样例输入 Copy
2
1 36
1 3636
样例输出 Copy
1 1
8 9
提示

[1, 3636]中36相关数有36, 360, 936,1368, 1836, 2736, 3600, 3636这8个, “36”出现了9次