1. 
/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest 
 * Problem:     11889 - Benefit
 * Link:        http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=226&problem=2989
 * 
 *
 * Method :     prime factorization
 * Status :     Accepted
 * Runtime:     0.676
 *
 * @author      Evgeni Pavlidis 
 * @version     1.0, 30/10/2010
 */


import java.io.*;
import java.util.*;

class Main 
{
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int nextInt() throws IOException
    {
        st.nextToken();
        return (int)st.nval;
    }

    static final int MAX = 10000000;
    static final int LIMIT = (int)Math.sqrt(MAX);
    static final boolean isPrime[] = new boolean[LIMIT+1];
    static final int[] prime = new int[LIMIT];
    static int maxPrime = 0;

    static int gcd(int a, int b)
    {
        return (b == 0? a: gcd(b, a%b));
    }

    static void sievePrimes()
    {
        prime[maxPrime++] = 2;
        for(int i = 3; i <= LIMIT; i+=2)
            isPrime[i] = true;

        int squareRoot = (int)Math.sqrt(LIMIT+1);
        for(int i = 3; i <= squareRoot; i+=2)
            if(isPrime[i])
                for(int j = i+i; j <= LIMIT; j+=i)
                    isPrime[j] = false;

        for(int i = 3; i <= LIMIT; i += 2)
            if(isPrime[i])
                prime[maxPrime++] = i;
    }

    static int f(int a, int c, int common)
    {
        int result = 1;
        int p;

        for(int i = 0; i < maxPrime && prime[i] <= common; i++)
            if(common % prime[i] == 0)
            {
                p = prime[i];
                while(c % (p*prime[i]) == 0)
                    p = p*prime[i];

                c /= p;

                if(a % p != 0)
                    result *= p;
            }

        if(a % c != 0)
            result *= c;

        return result;
    }

    public static void main(String...args) throws IOException
    {
        StringBuffer output = new StringBuffer();
        int testCases = nextInt();
        int a,c,b,common, t;

        sievePrimes();

        for(int tc = 0; tc < testCases; tc++)
        {
            a = nextInt();
            c = nextInt();

            if(a > c || c % a != 0)
                output.append("NO SOLUTION\n");
            else
            {
                common = gcd(a,c);
                t = c;
                while(gcd(a, t) > 1)
                    t /= gcd(a,t);

                output.append(t*f(a,c/t,common) + "\n");
            }
        }
        
        System.out.print(output);
    }
}