Anica 正在做一个奇特的梦。她梦见了一个无限大的棋盘。在这个棋盘上，画着一个由无限行 and 无限列组成的无限表格，其中包含着无限多个数字。有趣的是，表格中的每个数字都只出现了有限次。

这个表格的形状极其规则，其数值满足一个简单的递推关系。每行的第一个单元格包含该行的行号。不处于第一列的单元格的值，可以通过将其左侧单元格中的数字与该数字在十进制表示下的翻转数相加来计算。

形式化地，如果 $A(i, j)$ 表示第 $i$ 行第 $j$ 列的值，则满足：

• $A(i, 1) = i$
• $A(i, j) = A(i, j - 1) + \text{rev}(A(i, j - 1))$，对于每个 $j > 1$

其中 $\text{rev}(x)$ 表示将十进制表示下的数字 $x$ 按位翻转后得到的数字。例如，$\text{rev}(213) = 312$，$\text{rev}(406800) = 008604 = 8604$。

表格的前几行和前几列。请注意，该表格仅在两个方向上是无限的。

Anica 对这个棋盘并没有表现出太大的兴趣，漫不经心地走过了它。在棋盘后面，她注意到一盏灯，立刻吸引了她的注意。Anica 也引起了灯的注意，于是友好的精灵 Božo 从中走了出来。

“Anica！如果你能正确回答我的 $Q$ 个询问，你就能赢得一包 Dorina 威化饼干或 Domaćica 饼干，这完全取决于你自己的选择！我不想强加我的观点，但依我个人之见，Dorina 威化饼干更好吃。每个询问将包含两个整数 $A$ 和 $B$。你必须回答在棋盘上，处于区间 $[A, B]$ 内的数字一共出现了多少次。”

遗憾的是，Anica 无法回答这些询问，然后就醒了。

“啊，我没能赢得 Dorina 饼干，但至少我为 COCI 出了道题，”她想，然后继续忙自己的事情去了。

输入格式

第一行包含一个整数 $Q$ ($1 \le Q \le 10^5$)，表示询问的次数。

接下来的 $Q$ 行，每行包含两个整数 $A$ 和 $B$ ($1 \le A \le B \le 10^{10}$)，表示询问的区间。

输出格式

输出的第 $i$ 行必须包含一个整数，表示第 $i$ 个询问的答案。

子任务

对于占总分 50% 的测试数据，满足 $1 \le A \le B \le 10^6$。

样例

输入格式 1

2
1 10
5 8

输出格式 1

18
8

输入格式 2

3
17 144
121 121
89 98

输出格式 2

265
25
10

输入格式 3

1
1 1000000000

输出格式 3

1863025563