Hexadecimal numbers

 Problem:-

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

$$\begin{gathered} 1\le T\le \mathbb{50} \\ 1\le L,R\le {\mathbb{10}}^{\mathbb{5}} \end{gathered}$$

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;

    }

}