题目描述

小明很喜欢喜欢数字 1 ，他想研究两个整数之间所有整数出现了多少个数字 1 。

现在他想求 n 次，a 和 b 之间（包含 a 和 b ）的所有整数的 1 出现的次数，聪明的你能够帮帮小明吗？

输入格式

第 1 行 1 个整数 n ( 1 <= n <= 1000000 )。

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

输出格式

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

样例

3
1 10
10 20
5 9

2
11
0