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