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$ 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

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;
}
}