/

Algorithms, Brute Force, C++, Searching

Problem
Editorial
Analytics

You are given a range $[L,\ R]$. You are required to find the number of integers $X$ in the range such that $GCD(X,F(X)) > 1$ where $F(X)$ is equal to the sum of digits of $X$ in its hexadecimal (or base 16) representation.

For example, $F(27) = 1 + B = 1 + 11 = 12$ ($27$ in hexadecimal is written as $1B$). You are aksed $T$ such questions.

Input format

• The first line contains a positive integer $T$ denoting the number of questions that you are asked.
• Each of the next $T$ lines contain two integers $L$ and $R$ denoting the range of questions.

Output Format

For each test case, you are required to print exactly $T$ numbers as the output.

Constraints

$1 \leq T \leq \mathbb{50}\\ 1 \leq L,\ R \leq \mathbb{10^5}$

SAMPLE INPUT
3
1 3
5 8
7 12
SAMPLE OUTPUT
2
4
6
Explanation

For the first test-case, numbers which satisfy the criteria specified are : 2,3. Hence, the answer is 2.

For the second test-case, numbers which satisfy the criteria specified are : 5,6,7 and 8. Hence the answer is 4.

For the third test-case, numbers which satisfy the criteria specified are : 7,8,9,10,11 and 12. Hence the answer is 6.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB