Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with t pairs of integers p_i and q_i and for each pair decided to find the greatest integer x_i, such that: 

  * p_i is divisible by x_i; 
  * x_i is not divisible by q_i. 

Oleg is really good at division and managed to find all the answers quickly, how about you?

Input

The first line contains an integer t (1 ≤ t ≤ 50) — the number of pairs.

Each of the following t lines contains two integers p_i and q_i (1 ≤ p_i ≤ 10^{18}; 2 ≤ q_i ≤ 10^{9}) — the i-th pair of integers.

Output

Print t integers: the i-th integer is the largest x_i such that p_i is divisible by x_i, but x_i is not divisible by q_i.

One can show that there is always at least one value of x_i satisfying the divisibility conditions for the given constraints.

Example

Input


3
10 4
12 6
179 822


Output


10
4
179

Note

For the first pair, where p_1 = 10 and q_1 = 4, the answer is x_1 = 10, since it is the greatest divisor of 10 and 10 is not divisible by 4.

For the second pair, where p_2 = 12 and q_2 = 6, note that 

  * 12 is not a valid x_2, since 12 is divisible by q_2 = 6; 
  * 6 is not valid x_2 as well: 6 is also divisible by q_2 = 6. 

The next available divisor of p_2 = 12 is 4, which is the answer, since 4 is not divisible by 6.


/*import com.sun.org.apache.xpath.internal.operations.Bool;
import org.omg.CORBA.INTERNAL;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;
import java.io.*;
import java.math.*;


public class CC
{

//INPUT READER//

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int Int() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String String() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return String();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void flush() {
            writer.flush();
        }
    }

    static InputReader in = new InputReader(System.in);
    static OutputWriter out = new OutputWriter(System.out);
    static int modulus = (int) 1e7;

    public static int[] sort(int[] a) {
        int n = a.length;
        ArrayList<Integer> l = new ArrayList<>();
        for (int i : a)
            l.add(i);
        Collections.sort(l);
        for (int i = 0; i < l.size(); i++)
            a[i] = l.get(i);
        return a;
    }

    public static long pow(long a, long b){
        long result=1;
        while(b>0){
            if (b % 2 != 0){
                result=(result*a);
                b--;
            }
            a=(a*a);
            b /= 2;
        }
        return result;
    }

    public static long gcd(long x, long y) {
        if (x == 0)
            return y;
        else
            return gcd(y % x, x);
    }

    public static long lcm(long x, long y) {
        return (x * (y / gcd(x, y)));
    }

    public static int i() {
        return in.Int();
    }

    public static long l() {
        String s = in.String();
        return Long.parseLong(s);
    }

    public static String s() {
        return in.String();
    }

    public static int[] readArray(int n) {
        int A[] = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = i();
        }
        return A;
    }

    public static long[] readArray(long n) {
        long A[] = new long[(int) n];
        for (int i = 0; i < n; i++) {
            A[i] = l();
        }
        return A;
    }

    static class pair {
        int x;
        int y;

        pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static ArrayList<ArrayList<Integer>> graph;

    static ArrayList<Integer> bfs(ArrayList<ArrayList<Integer>> g, int n, int src) {
        ArrayList<Integer> p = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        Boolean visited[] = new Boolean[n];
        Arrays.fill(visited, false);

        visited[src] = true;
        q.add(src);
        while (q.size() != 0) {
            src = q.poll();
            p.add(src);
            Iterator<Integer> it = g.get(src).iterator();
            while (it.hasNext()) {
                int nn = it.next();

                if (visited[nn] == false) {
                    visited[nn] = true;
                    q.add(n);

                }
            }

        }
        return p;

    }





    public static void main(String[] args)
    {

        StringBuffer sb = new StringBuffer();
            int t=i();
            while (t-->0) {
                long p = i();
                long q = i();
                long x = 1;
                 if(p%q==0)
                 {
                     long num = q;
                    TreeMap<Long,Integer>h=new TreeMap<>();
                     for (int i = 2; i <= Math.sqrt(q); i++)
                     {

                         if (num% i == 0)
                         {
                             int cnt = 0;
                             while (num % i == 0)
                             {
                                 num=num/i;
                                 cnt++;
                             }
                             h.put((long)i,cnt);
                         }
                     }
                     if(num!=1)
                      h.put(num,1);
                     long ans=1;
                     long minimumkey=Long.MAX_VALUE;
            BigInteger f=new BigInteger("1");
                     for(Map.Entry<Long,Integer> hm:h.entrySet())
                     {
                         BigInteger love;
                         long key=(long)hm.getKey();
                         long freq=(long)hm.getValue();
                        long value=pow(key,freq);
                       long g=p/value;
                         while(g%key==0)
                         {
                            g=g/key;
                         }
                       love=BigInteger.valueOf(g*pow(key,(freq-1)));
                         int cv=love.compareTo(f);
                         if(cv==1)
                             f=love;

                     }

                    sb.append(f+"\n");






                 }
                 else
                     sb.append(p+"\n");

                if (p < q) {
                    sb.append(p + "\n");
                } else if (p % q != 0) {
                    sb.append(p + "\n");
                } else {
                    long num = q;
                    HashMap<Long, Integer> hash = new HashMap<>();
                    for (long i = 2; i <= Math.sqrt(q); i++) {
                        if (num % i == 0) {
                            int count = 0;
                            while (num % i == 0) {
                                num = num / i;
                                count++;
                            }
                            hash.put(i, count);
                        }
                    }
                    if (num != 1) {
                        hash.put(num, 1);
                    }
                    long ans = 1;
                    for (Map.Entry<Long, Integer> entry : hash.entrySet()) {
                        long tmp = entry.getKey();
                        long freq = entry.getValue();
                        long num1 = p / pow(tmp, freq);
                        int pp = 0;
                        while (num1 % tmp == 0) {
                            num1 = num1 / tmp;
                            pp++;
                        }
                        long rem = freq - 1;
                        ans = Math.max(num1 * 1L * pow(tmp, rem), ans);
                    }
                    sb.append(ans+"\n");
                }





            }
            System.out.println(sb.toString());




    }
}*/
import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.io.*;
import java.math.*;
public class CC{
    static public void main(String args[])throws IOException{
        int tt=i();
        StringBuilder sb=new StringBuilder();
        for(int ttt=1;ttt<=tt;ttt++)
        {
            long p=l();
            long q=l();

            if(p%q==0) {
                long num = q;
                TreeMap<Long, Integer> h = new TreeMap<>();
                for (int i = 2; i <= Math.sqrt(q); i++) {

                    if (num % i == 0) {
                        int cnt = 0;
                        while (num % i == 0) {
                            num = num / i;
                            cnt++;
                        }
                        h.put((long) i, cnt);
                    }
                }
                if (num != 1)
                    h.put(num, 1);
                long ans = 1;
                long minimumkey = Long.MAX_VALUE;
                BigInteger f = new BigInteger("1");
                for (Map.Entry<Long, Integer> hm : h.entrySet()) {
                    BigInteger love;
                    long key = (long) hm.getKey();
                    long freq = (long) hm.getValue();
                    long value = pow(key, freq);
                    long g = p / value;
                    while (g % key == 0) {
                        g = g / key;
                    }
                    love = BigInteger.valueOf(g * pow(key, (freq - 1)));
                    int cv = love.compareTo(f);
                    if (cv == 1)
                        f = love;

                }

                sb.append(f + "\n");
            }
            else
                sb.append(p+"\n");




            }
        System.out.print(sb.toString());
    }

    static InputReader in=new InputReader(System.in);
    static OutputWriter out=new OutputWriter(System.out);
    static ArrayList<ArrayList<Integer>> graph;
    static int mod=1000000007;
    static class Pair{
        long x;
        int y;
        int z;
        Pair(long x,int y,int z){
            this.x=x;
            this.y=y;
            this.z=z;
        }
		/*@Override
		public int hashCode()
		{
			final int temp = 14;
			int ans = 1;
			ans =x*31+y*13;
			return (int)ans;
		}
       @Override
        public boolean equals(Object o)
        {
            if (this == o) {
                return true;
            }
            if (o == null) {
                return false;
            }
            if (this.getClass() != o.getClass()) {
                return false;
            }
            Pair other = (Pair)o;
            if (this.x != other.x || this.y!=other.y) {
                return false;
            }
            return true;
        }*/
    }
    public static int[] sort(int[] a){
        int n=a.length;
        ArrayList<Integer> ar=new ArrayList<>();
        for(int i=0;i<a.length;i++){
            ar.add(a[i]);
        }
        Collections.sort(ar);
        for(int i=0;i<n;i++){
            a[i]=ar.get(i);
        }
        return a;
    }
    public static long pow(long a, long b){
        long result=1;
        while(b>0){
            if (b % 2 != 0){
                result=(result*a);
                b--;
            }
            a=(a*a);
            b /= 2;
        }
        return result;
    }
    public static long gcd(long a, long b){
        if (a == 0){
            return b;
        }
        return gcd(b%a, a);
    }
    public static long lcm(long a, long b){
        return a*(b/gcd(a,b));
    }
    public static long l(){
        String s=in.String();
        return Long.parseLong(s);
    }
    public static void pln(String value){
        System.out.println(value);
    }
    public static int i(){
        return in.Int();
    }
    public static String s(){
        return in.String();
    }
}
class InputReader
{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;
    public InputReader(InputStream stream) {
        this.stream = stream;
    }
    public int read() {
        if (numChars== -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
    public int Int() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    public String String() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
    public String next() {
        return String();
    }
    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}
class OutputWriter {
    private final PrintWriter writer;
    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }
    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }
    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }
    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }
    public void close() {
        writer.close();
    }
    public void flush() {
        writer.flush();
    }
}










