小明很喜欢喜欢数字1，他想研究两个整数之间所有整数出现了多少个数字1。 现在他想求n次，a和b之间（包含a和b）的所有整数的1出现的次数，聪明的你能够帮帮小明吗？

输入格式

第一行一个整数n(1<=n<=1000000)。 下面有n行，每行 2 个整数 a 和 b(1<=a,b<=1000000)。

输出格式

n个整数，每个数一行，对应 n个询问。

输入/输出例子1

输入：

3

1 10

10 20

5 9

输出：

2

11

0