Distinct Digit Numbers

For each closed range of positive integers, count the integers whose decimal representation has no repeated digit. For the original example [9,84] the answer should be 69; the original 47 is wrong, and its list omits 84.

输入格式

The first line contains q, followed by q lines of lower upper. Original bound 1≤q≤100000; the original upper bound on the endpoints is truncated, so this site adds 1≤lower≤upper≤1000000.

输出格式

Output q lines of counts, one for each closed range in order.

样例 1

输入：

2
1 20
9 19

输出：

19
10

样例 2

输入：

5
7 8
52 80
9 84
57 64
74 78

输出：

2
26
69
8
4

样例 3

输入：

1
80 120

输出：

27

样例说明

The outputs of the three public examples are, in order: 19 / 10; 2 / 26 / 69 / 8 / 4; 27. These answers have been checked by independent enumeration or direct simulation.