Ragu has given a range (L, R] to Smith. Smith wants to require to find the number of integers ‘X’ in the range such that (Greatest common divisor) GCD(X, F(X)) > 1 where F(x) is equal to the sum of digits of ‘X’ in its hexadecimal (or base 16) representation.

Example: F(27) = 1+B=1+11=12 (27 in hexadecimal is written as 1B)

Constraints:

1 <= T <= 50

1 <= L

R <= 10^5

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:

Print the output in a separate lines exactly ‘T’ numbers as the output.

#include<bits/stdc++.h> using namespace std; int F(int x) //hexadeciaml { int sum = 0; while(x > 0) { sum += x%16; x = x/16; } return sum; } int search(int a, int b) { int count=0; for(int i=a;i<=b;i++) { if(__gcd(i,F(i))>1) count++; } return count; } int main() { int t,l,r; cout<<"Enter the T number: "; cin>>t; while(t--) { cout<<"Enter range L and R : "; cin>>l>>r; int count=search(l,r); cout<<"Number of integers: "<<count<<endl; } }

**Output_1:**Enter the T number: 2

Enter range L and R : 100 200

Number of integers: 62

Enter range L and R : 50 70

Number of integers: 13

**Output_2:**Enter the T number: 2

Enter range L and R : 1000 1500

Number of integers: 309

Enter range L and R : 3500 6000

Number of integers: 1547

**Output_3:**Enter the T number: 1

Enter range L and R : 1000 20000

Number of integers: 11854

**Output_4:**Enter the T number: 1

Enter range L and R : 1000 100000

Number of integers: 61817

**Output_5:**Enter the T number: 3

Enter range L and R : 500 800

Number of integers: 189

Enter range L and R : 5000 15000

Number of integers: 6230

Enter range L and R : 2300 6000

Number of integers: 2303

ScrShot