Ten Ranges
시간 제한2초메모리 제한512 MB
각 구간 [l, r]에서 소수인 십진 부분수열을 하나도 포함하지 않는 정수의 개수를 센다. r은 10^18까지이다.
문제
An integer x is called a decimal subsequence of an integer y if the decimal representation of x can be obtained from the decimal representation of y by erasing some digits (possibly none, but not all).
An integer x is called a prime if x ≥ 2 and its only positive integer divisors are 1 and x.
An integer x is called secondary if there is no integer y such that y is a decimal subsequence of x and y is a prime.
For example, 168 is secondary as none of 1, 6, 8, 16, 18, 68, 168 is a prime, while 169 is not secondary as 19 is a prime.
Find the number of secondary integers in each of the given ranges [l; r].
입력
The first line of the input contains a single integer n (1 ≤ n ≤ 10), denoting the number of ranges.
Each of the following n lines contains two integers l and r (1 ≤ l ≤ r ≤ 1018), denoting the boundaries of the range.
출력
Display the number of secondary integers in each of the given ranges, in order of input.
힌트
In the example test case, secondary integers belonging to [8; 16] are 8, 9, 10, 14, and 16, and secondary integers belonging to [157; 174] are 160, 164, 166, and 168.