怪盗的谜题

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

 

“怪盗绅士” 布卢布兰是一个很奇怪的人,他在卢安地区给艾丝蒂尔一行人设下了许多谜题。

今天小艾也得到了一个新的谜题:

 

怪盗非常喜欢数字,并且特别喜欢回文数,例如 “12321“,现在我们定义这样数的价值是每一位相乘,例如 "12321" 的价值是 1 × 2 × 3 × 2 × 1 = 12,”77777“ 就是 7^5。

但是对其他的数字怪盗并不感兴趣,定义他们的价值为各位数字和,例如 ”12345“ 的价值为 1 + 2 + 3 +4 + 5 = 15。

 

怪盗可以说是对数字非常痴迷,他现在想知道从 l 到 r 的数字中,价值和为多少,例如 1 到 9 中,价值和为  1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45。

 

众所周知小艾的数学并不好,所以现在想要你编写程序帮助她解决这个问题。

如果你解决了这个问题,提妲将会送给你一个 Accepted。

 

 

甚至你可以得到奥利维尔的一个吻。

 

Input

单组测试数据。

首先输入一个整数 QAQ,表示接下来有 QAQ 次询问。(1 <= QAQ <= 100000)

每次询问会输入两个整数 l 和 r,表示从 l 到 r 的数。(1 <= l <= r <= 100000)

Output

对于每次询问输出一行答案。

Sample Input

2
1 9
11 12

Sample Output

45
4

Hint

Source

Fish