Stjepan 最近获得了萨格勒布大学（University of Zagreb）的数学学士学位。自然地，他的父母感到非常自豪，并决定送给他所有不超过 $2^{60}$ 的正整数作为礼物。为了安全起见，他迅速将所有这些数字存储在一个数组 $A$ 中，使得 $A_i = i$。

他嫉妒的朋友 Marin 决定对他开个玩笑，方法是重复地将 $A$ 的每个元素替换为其各位数字之和，直到 $A$ 的所有元素都由单个数字组成。例如，$A$ 的第 $197$ 个元素的初始值为 $197$。Marin 首先将该值更改为 $1 + 9 + 7 = 17$，然后再次将其值更改为 $1 + 7 = 8$。

Stjepan 感到非常沮丧，并恳求 Marin 将他的数组恢复到初始状态。不幸的是，除非 Stjepan 正确回答他的 $Q$ 个询问，否则 Marin 不会这样做：“从 $A$ 的第 $l$ 个元素到第 $r$ 个元素的数字之和是多少？”。

帮助 Stjepan 回答这些询问！

输入格式

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

接下来的 $Q$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le 2^{60}$)，表示 Marin 的第 $i$ 次询问的参数。

输出格式

输出 Marin 的 $Q$ 次询问中每一次的答案。每个答案应单独打印在一行中，且它们的顺序应与输入中给出的询问顺序相匹配。

子任务

在价值 10 分的测试用例中，对于每个询问，满足 $1 \le l_i \le r_i \le 9$。

在价值 30 分的测试用例中，对于每个询问，满足 $r_i - l_i \le 1000$。

样例

输入样例 1

1
1 5

输出样例 1

15

输入样例 2

2
9 13
44 45

输出样例 2

19
17

输入样例 3

1
1998 2018

输出样例 3

102

说明

样例 2 解释：

第 1 次询问 $\rightarrow A_9 = 9, A_{10} = 1 + 0 = 1, A_{11} = 1 + 1 = 2, A_{12} = 1 + 2 = 3, A_{13} = 1 + 3 = 4$。 $A_9 + A_{10} + A_{11} + A_{12} + A_{13} = 9 + 1 + 2 + 3 + 4 = 19$。

第 2 次询问 $\rightarrow A_{44} = 4 + 4 = 8, A_{45} = 4 + 5 = 9$。$A_{44} + A_{45} = 8 + 9 = 17$。