All Tracks Algorithms Searching Linear Search Problem

Hexadecimal numbers
/

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?