Description

我们称一个正整数n是好的，当且仅当n能被他的所有数位整除。 现在需要计算在一个给定的区间[l, r]中的好数的个数。

Format

Input

第一行，询问数t。

下面t行，每行两个数l, r，表示询问的区间。

Output

对于每个询问输出一行表示答案。

Samples

1
1 100

33

Hint

30%的数据 r<=10^7

另30%的数据 t<=100

100%的数据 t<=2.5*10^4, 1<=l<=r<=10^18