Background

已知两个正整数a和b，求在a与b之间（包含a和b）的所有整数的十进制表示中1出现的次数。n组数据(n<=100000)，每组数据2个整数a，b.(1≤a,b≤1000000).每组数据的答案占一行。

Input

第一行为整数n，接下来n行，每行2个数，分别是a和b

Output

输出n行，每行表示从a到b中所有数中1出现的次数。

Samples

3
1 10
10 100
2 1

2
20
1