The Great Ninja War is going on. Naruto got some information from his spy that there are some special troops in the enemy's army. Troops are numbered starting from 1.

Special Troops are described as follows :-
Let's say the troop number consists of N digits given as {\(D_{1},D_{2},D_{3},.....,D_{N}\)}, for which the special sum S will be \(\sum_{i=1}^{N} {D_{i}}^{D_{i}}\) \(\forall\) \(D_{i} \neq 0\).
If all the digits \(D_{i}\) \(\forall\) \(i \in [1,N]\) and \(D_i \neq 0\) of that number completely divide the special sum S, then the troop is special.
For example, consider the troop number \(2024\), the special sum S will be \(2^{2} + 2^{2} + 4^{4} = 264\). As all the non-zero digits 2, 2 and 4 completely divide \(264\), hence the troop is special.

Naruto asked you to find the number of special troops numbered between L and R (both inclusive).

INPUT FORMAT
The first line of input contains a single integer Q denoting the number of testcases.
Each of the next Q lines consist of two space separated integers L and R.

OUTPUT FORMAT
The output should consist of Q lines each consisting of a single integer denoting the answer to the question.

CONSTRAINTS

• \(1 \le Q \le 3\)
• \(1 \le L \le R \le 10^{12}\)