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 java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

/**
 * @author htdong
 * @date 2018年4月20日 上午11:52:19
 */

public class Main {

    static int[] a = new int[40010];
    static boolean[] f = new boolean[40010];

    public static long f(int a, int b) {
        long c = 1;
        for (int i = 1; i <= b; ++i) {
            c *= a;
        }
        return c;
    }

    public static void main(String[] args) {
        a[0] = 0;
        for (int i = 2; i <= 40000; ++i) {
            if (!f[i]) {
                a[++a[0]] = i;
            }
            for (int j = i + i; j <= 40000; j += i) {
                f[j] = true;
            }
        }

        Scanner in = new Scanner(System.in);
        int _t = in.nextInt();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        TreeMap<Integer, Integer> m2 = new TreeMap<>();
        while (_t-- > 0) {
            map.clear();
            m2.clear();
            long n = in.nextLong();
            long m = in.nextLong();
            if (n % m != 0) {
                System.out.println(n);
                continue;
            }
            for (int i = 1; i <= a[0] && m > 1; ++i) {
                while (m % a[i] == 0) {
                    m /= a[i];
                    map.put(a[i], map.getOrDefault(a[i], 0) + 1);
                }
            }
            if (m > 1) {
                map.put((int) m, 1);
            }
            for (Map.Entry<Integer, Integer> iter : map.entrySet()) {
                int s = 0;
                long b = n;
                while (b % iter.getKey() == 0) {
                    b /= iter.getKey();
                    ++s;
                }
                m2.put(iter.getKey(), s - iter.getValue() + 1);
            }
            long ans = 0;
            for (Map.Entry<Integer, Integer> iter : m2.entrySet()) {
                ans = Math.max(ans, n / f(iter.getKey(), iter.getValue()));
            }
            System.out.println(ans);
        }
        in.close();
    }

    public static int idx(int l, int r) {
        return (l + r) | (l != r ? 1 : 0);
    }

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

    public static long pow(long a, int n, long mod) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) > 0) {
                ans = ans * a % mod;
            }
            a = a * a % mod;
            n >>= 1;
        }
        return ans;
    }

    static class TreapNode {
        int key, val;
        int wht, sz;
        TreapNode[] ch;
        private static TreapNode LEAF = null;
        // private static final Random RAND = new Random(System.currentTimeMillis());
        private static int x = 1364684679;

        static int rands() {
            x += (x << 2) + 1;
            return x;
        }

        public static TreapNode leaf() {
            if (LEAF != null) {
                return LEAF;
            }
            LEAF = new TreapNode();
            LEAF.ch = new TreapNode[2];
            LEAF.ch[0] = LEAF.ch[1] = LEAF;
            LEAF.sz = 0;
            LEAF.key = -1;
            LEAF.val = -1;
            LEAF.wht = -2147483648;
            return LEAF;
        }

        private TreapNode() {
        }

        public TreapNode(int key, int val) {
            ch = new TreapNode[2];
            ch[0] = ch[1] = leaf();
            this.key = key;
            this.val = val;
            this.sz = 1;
            this.wht = rands();
        }

        @Override
        public String toString() {
            return "key= " + key + ", val = " + val;
        }
    }

    static class Treap {

        private TreapNode root, leaf;

        public Treap() {
            leaf = TreapNode.leaf();
            root = leaf;
        }

        public void insert(int key, int val) {
            insert(root, key, val, null, 0);
        }

        public void remove(int key) {
            remove(root, key, null, 0);
        }

        public int find(int key) {
            return find(root, key);
        }

        public int findLowerOrEqual(int key) {
            TreapNode rlt = findLowerOrEqual(root, key);
            return rlt == leaf ? -1 : rlt.key;
        }

        public int findUpperOrEqual(int key) {
            TreapNode rlt = findUpperOrEqual(root, key);
            return rlt == leaf ? -1 : rlt.key;
        }

        public int maxKey() {
            TreapNode t = root;
            while (t.ch[1] != leaf) {
                t = t.ch[1];
            }
            return t.key;
        }

        public int size() {
            return root.sz;
        }

        private void insert(TreapNode x, int key, int val, TreapNode px, int pt) {
            if (x == leaf) {
                x = new TreapNode(key, val);
                if (px != null) {
                    px.ch[pt] = x;
                } else {
                    root = x;
                }
                return;
            }
            if (key == x.key) {
                x.val = val;
            } else {
                int son = key < x.key ? 0 : 1;
                insert(x.ch[son], key, val, x, son);
                if (x.wht < x.ch[son].wht) {
                    rotate(x, son, px, pt);
                }
            }
            update(x);
        }

        private void remove(TreapNode x, int key, TreapNode px, int pt) {
            if (x == leaf) {
                return;
            }
            if (x.key == key) {
                if (x.ch[0] == leaf && x.ch[1] == leaf) {
                    if (px == null) {
                        root = leaf;
                    } else {
                        px.ch[pt] = leaf;
                    }
                    return;
                }
                int son = x.ch[0].wht > x.ch[1].wht ? 0 : 1;
                rotate(x, son, px, pt);
                remove(x, key, px == null ? root : px.ch[pt], son ^ 1);
            } else {
                int son = key < x.key ? 0 : 1;
                remove(x.ch[son], key, x, son);
            }
            update(x);
        }

        private int find(TreapNode x, int key) {
            if (x == leaf) {
                return -1;
            }
            if (x.key == key) {
                return x.val;
            }
            return find(x.ch[key < x.key ? 0 : 1], key);
        }

        private TreapNode findLowerOrEqual(TreapNode x, int key) {
            if (x == leaf) {
                return leaf;
            }
            if (x.key == key) {
                return x;
            }
            if (x.key > key) {
                return findLowerOrEqual(x.ch[0], key);
            }
            TreapNode lv = findLowerOrEqual(x.ch[1], key);
            if (lv == leaf || lv.key > key) {
                return x;
            } else {
                return lv;
            }
        }

        private TreapNode findUpperOrEqual(TreapNode x, int key) {
            if (x == leaf) {
                return leaf;
            }
            if (x.key == key) {
                return x;
            }
            if (x.key < key) {
                return findUpperOrEqual(x.ch[1], key);
            }
            TreapNode lv = findUpperOrEqual(x.ch[0], key);
            if (lv == leaf || lv.key < key) {
                return x;
            } else {
                return lv;
            }
        }

        private void update(TreapNode t) {
            t.sz = 1 + t.ch[0].sz + t.ch[1].sz;
        }

        private void rotate(TreapNode x, int t, TreapNode px, int pt) {
            TreapNode s = x.ch[t];
            x.ch[t] = s.ch[t ^ 1];
            s.ch[t ^ 1] = x;
            update(x);
            update(s);
            if (px != null) {
                px.ch[pt] = s;
            } else {
                root = s;
            }
        }
    }
}