Description

阿瓦是一只自称萝莉的小花猫，她生活在叮想世界。 解决了炸弹礼物的烦恼之后，她䮦间又对世界恢复了信心。这天她来到数字花园，她一下子就被绽放的花朵给迷住了。兔阿卡观察到了这一点，决定购买一些阿瓦比较喜欢的花朵，拿回去送给阿瓦。

数字花园的每一朵花上都有一个 1 到 $10^9$ 的数字，这些数字决定了花朵的美丽程度。 但阿卡觉得，如果直接问阿瓦喜欢哪些花，这样就太不够惊喜了。但他知道，阿瓦的幸运数字是 6 和 9 。因此他猜測，如果一个数字在六进制下 1 的个数与这个数字在九进制下 1 的个数相差不超过 1 ，那么阿瓦就喜欢这朵花。换一种方法讲，假设这个数字在六进制下 1 的个数为 $x$ ，在九进制下 1 的个数为 $y$ ，当 $|x-y| \leq 1$ ，即 $-1 \leq x-y \leq 1$ 时，这个数字对应的花是被阿瓦所喜欢的。

1 的个数在这里是指数位中 1 的个数，比如 10294851 中有 2 个 1,111 中有 3 个 1 。 数字花园当中有若干个人口，每个人口中的花朵上的数字都在一个连续的范围内。数字花园中没有两朵花的数字是一样的，也就是说，所有的花朵上的数字都是不相同的。一个人口里面花朵的个数为这个人口对应数字范围的区间大小。例如如果一个人口的数字范围是 $[2,5]$ ，那么这个人口里面就有 4 朵花。因为区间 $[2,5]$ 中一共包含了 4个正整数 $\{2,3,4,5\}$ 。

阿卡在所有的人口中挑选了 $T$ 个人口，他已经知道了这些人口对应的范围，想要让你来邦仙计算，每一个人口中有多少朵花是阿瓦喜㰠的。

Format

Input

第一行，一个整数 $T$ ，代表阿卡挑选出的人口个数。 接下来 $T$ 行，每行两个整数 $L, R$ 。 表示这个人口对应的范围是 $[L, R]$ 。

Output

输出 $T$ 行，对于每一个人口，都输出一个数表示这个人口中有多少朵花是阿瓦喜欢的。

Samples

3
1 3
2 10
34 1258

3
8
1012

Limitation

对于 $50 \%$ 的数据，$T=1,1 \leq L \leq R \leq 10^3$ 。

对于 $70 \%$ 的数据，$T \leq 10,1 \leq L \leq R \leq 10^5$ 。

对于 $100 \%$ 的数据，$T \leq 10^5, 1 \leq L \leq R \leq 10^5$ ．