Divisors and Reciprocals:

Alice is teaching Bob maths via a game called N$N$-guesser.

Alice has a positive integer N$N$ which Bob needs to guess. She gives him two pieces of information with which to do this:

• A positive integer X$X$, which denotes the sum of divisors of N$N$.
• Two positive integers A$A$ and B$B$, which denote that the sum of reciprocals of divisors of N$N$ is A/B$A/B$.

Bob either needs to guess N$N$ or tell that no such number exists.

It can be shown that if a valid N$N$ exists, it is unique.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• Each test case consists of a single line of input, containing three space-separated integers X,A,B$X,A,B$.

Output Format

For each test case, output a new line containing the answer — Alice's number N$N$, or −1$-1$ if no such number exists.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤X≤109$1\le X\le {10}^9$
• 1≤A,B≤109$1\le A,B\le {10}^9$
• gcd(A,B)=1$gcd(A,B)=1$

Sample Input 1 

2
4 4 3
4 1 1

Sample Output 1 

3
-1

Explanation

Test case 1$1$: The divisors of 3$3$ are 1$1$ and 3$3$. Their sum is 4$4$ and the sum of their reciprocals is 4/3$4/3$.

Test case 2$2$: It can be proved that no positive integer N$N$ exists whose divisors sum to 4$4$ and reciprocals of divisors sum to 1$1$.

SOLUTION:

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

int main()

{

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int tt=1;cin>>tt;

    while(tt--)

    {

        ll x,a,b;cin>>x>>a>>b;

        if(x%a==0)

        {

            ll p=x/a;

            ll den=b*p;

            ll sum=0;

            for(int i=1;i<=sqrtl(den);i++)

            {

                if(sum>x)

                break;

                if(den%i==0)

                {

                    sum=sum+i;

                    if(den/i!=i)

                    sum=sum+den/i;

                }

            }

            if(sum!=x)

            {

                cout<<-1<<"\n";

            }

            else

            cout<<den<<"\n";

        }

        else

        cout<<-1<<"\n";

    }

}