Problem:-

You are given a range

. You are required to find the number of integers

$X$

in the range such that

$GCD\left(X,F\left(X\right)\right)>1$

where

$F\left(X\right)$

is equal to the sum of digits of

$X$

in its hexadecimal (or base 16) representation.

For example,

$F\left(27\right)=1+B=1+11=12$

(

$27$

$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

Sample Input
3
1 3
5 8
7 12
Sample Output
2
4
6
Time Limit: 2
Memory Limit: 256
Source Limit:
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.

Code:-

#include<bits/stdc++.h>
using namespace std;

// function for calculate gcd
int gcd(int a,int b)
{
int n=a>b?b:a;
for(int i=n;i>1;i–)
{
if(a%i==0 && b%i==0)
return 0;
}
return 1;
}

//Driver function
int main()
{
int t,l,r;
cin>>t;
while(t–)
{
cin>>l>>r;
int ans=0;
for(int i=l;i<=r;i++)
{
int x=i;
int sum=0;
// lopgic for calculate Hexadecimal number
while(x!=0)
{
int r=x%16;
x=x/16;
sum=sum+r;
}
int f=gcd(i,sum);
// if gcd greater than 1 than return 0
if(f==0)
ans++;
}
cout<<ans<<endl;
}
}