11889 - Benefit

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define MAX 10000
using namespace std;
long long int divisor[MAX];
long long int G(long long int a,long long int b)
{
    long long int temp,gcd,m,n,lcm;
    m=a;
    n=b;
    while(b!=0)
    {
        temp=b;
        b=a%b;
        a=temp;
    }
    gcd=a;
    lcm=(m*n)/gcd;
    return lcm;
}
int main()
{
    long long int x,test_case,A,C,B,LCM,a,b,c,d,e,i,j,k;
    scanf("%lld",&test_case);
    while(test_case--)
    {
        scanf("%lld%lld",&A,&C);
        a=sqrt(C);
        k=0;
        for(i=1; i<=a; i++)
        {
            if(C%i==0)
            {
                b=C/i;
                if(i==b)
                {
                    divisor[k++]=i;
                }
                else
                {
                    divisor[k++]=i;
                    divisor[k++]=b;
                }
            }
        }
        sort(divisor,divisor+k);
        e=0;
        for(i=0; i<k; i++)
        {
            LCM=G(A,divisor[i]);
            if(LCM==C)
            {
                d=divisor[i];
                e++;
                break;
            }
        }
        if(e>0)
        {
            printf("%lld\n",d);
        }
        else
        {
            printf("NO SOLUTION\n");
        }
        memset(divisor,0,sizeof(divisor));
    }
    return 0;
}