SOLVE

LATER

Hexadecimal numbers

/

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}\)

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

Initializing Code Editor...