Problem: Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.

Input

The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9 ·1018).

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output

Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).

Examples

Input

1
1 9


Output

9


Input

1
12 15


Output

2

Solution (in JAVA):

Solution:
import java.util.*;

public class Main {
	public static int mod = 2520;
	public static int[] ord = new int[mod+10];
	public static long[] num = new long[25];
	public static long[][][] dp = new long[25][mod+10][50];//前X位 对2520取模后的和 当前的lcm
	public static void main(String[] args) {
		init();
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while ( t-->0 ) {
			long L = sc.nextLong();
			long R = sc.nextLong();
			System.out.println( solve(R) - solve(L-1) );	
		}
	} 
	public static int gcd( int x , int y ) {
		return y == 0 ? x : gcd( y , x%y );
	}
	public static void init() {
		int cnt = 0;
		for ( int i = 1 ; i<=mod ; ++i ) {
			if ( mod%i==0 ) {
				ord[i] = cnt++;
			}
		}
		for ( int i = 0 ; i<=22 ; ++i ) {
			for ( int j = 0 ; j<=mod ; ++j ) {
				for ( int k = 0 ; k<=48 ; ++k ) {
					dp[i][j][k] = -1L;
				}
			}
		}
	}
	public static long dfs( int prepos , int presum , int prelcm , boolean flag ) {
		if ( prepos==-1 ) {
			if ( presum%prelcm == 0 ) {
				return 1;
			} else {
				return 0;
			}
		}
		if ( !flag && dp[prepos][presum][ord[prelcm]]!=-1 ) {
			return dp[prepos][presum][ord[prelcm]];
		}
		int last = flag ? (int)num[prepos] : 9;
		long res = 0;
		for ( int i = 0 ; i<=last ; ++i ) {
			int nowsum = ( presum*10 + i ) % mod;
			int nowlcm = prelcm;
			if ( i>0 ) {
				nowlcm = nowlcm * i / gcd( nowlcm , i );
			}
			res += dfs( prepos-1 , nowsum , nowlcm , flag && i==last );
		}
		if ( !flag ) {
			dp[prepos][presum][ord[prelcm]] = res;
		}
		return res;
	}
	public static long solve( long x ) {
		int cnt = 0;
		while ( x>0 ) {
			num[cnt++] = x % 10;
			x /= 10;
		}
		return dfs( cnt-1 , 0 , 1 , true );
	}
}