Polycarp wants to buy exactly n shovels. The shop sells packages with shovels. The store has k types of packages: the package of the i-th type consists of exactly i shovels (1 ≤ i ≤ k). The store has an infinite number of packages of each type.

Polycarp wants to choose one type of packages and then buy several (one or more) packages of this type. What is the smallest number of packages Polycarp will have to buy to get exactly n shovels?

For example, if n=8 and k=7, then Polycarp will buy 2 packages of 4 shovels.

Help Polycarp find the minimum number of packages that he needs to buy, given that he: 

  * will buy exactly n shovels in total; 
  * the sizes of all packages he will buy are all the same and the number of shovels in each package is an integer from 1 to k, inclusive. 

Input

The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases in the input. Then, t test cases follow, one per line.

Each test case consists of two positive integers n (1 ≤ n ≤ 10^9) and k (1 ≤ k ≤ 10^9) — the number of shovels and the number of types of packages.

Output

Print t answers to the test cases. Each answer is a positive integer — the minimum number of packages.

Example

Input


5
8 7
8 1
6 10
999999733 999999732
999999733 999999733


Output


2
8
1
999999733
1

Note

The answer to the first test case was explained in the statement.

In the second test case, there is only one way to buy 8 shovels — 8 packages of one shovel.

In the third test case, you need to buy a 1 package of 6 shovels.

import java.io.*;
import java.math.*;
import java.util.*;
import javafx.util.Pair;

public class Level {

    public static DS.Scanner in = new DS.Scanner();
    public static DS.Print out = new DS.Print();

    public static void main(String[] args) {
        int Q = in.nextInt();
        while (Q-- > 0) {
            long n = in.nextInt();
            long k = in.nextInt();
            if (n <= k) {
                System.out.println(1);
            } else {
                ArrayList<Long> list = Algo.dd(n);
                if (list.contains(n)) {
                    list.remove(n);
                }
                Collections.sort(list, Collections.reverseOrder());
                long dv = 1;
                for (long val : list) {
                    if (val <= k) {
                        dv = val;
                        break;
                    }
                }
                long ans = 0;
                ans = n / dv;
                System.out.println(ans);
            }
        }
    }

    public static class Algo {

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

        public static int lowerBound(ArrayList<Long> list, int length, long value) {
            int low = 0;
            int high = length;
            while (low < high) {
                final int mid = (low + high) / 2;
                if (value <= list.get(mid)) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }

        public static int upperBound(ArrayList<Long> list, int length, long value) {
            int low = 0;
            int high = length;
            while (low < high) {
                final int mid = (low + high) / 2;
                if (value >= list.get(mid)) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
        }

        public static void merge(int arr[], int l, int m, int r) {
            int n1 = m - l + 1;
            int n2 = r - m;

            int L[] = new int[n1];
            int R[] = new int[n2];

            for (int i = 0; i < n1; ++i) {
                L[i] = arr[l + i];
            }
            for (int j = 0; j < n2; ++j) {
                R[j] = arr[m + 1 + j];
            }

            int i = 0, j = 0;

            int k = l;
            while (i < n1 && j < n2) {
                if (L[i] <= R[j]) {
                    arr[k] = L[i];
                    i++;
                } else {
                    arr[k] = R[j];
                    j++;
                }
                k++;
            }

            while (i < n1) {
                arr[k] = L[i];
                i++;
                k++;
            }

            while (j < n2) {
                arr[k] = R[j];
                j++;
                k++;
            }
        }

        public static void sort(int arr[], int l, int r) {
            if (l < r) {
                int m = (l + r) / 2;

                sort(arr, l, m);
                sort(arr, m + 1, r);

                merge(arr, l, m, r);
            }
        }

        public static ArrayList<Integer> sieve(int n) {
            long sqr = (long) Math.sqrt(n);
            boolean[] isPrime = new boolean[n + 1];
            for (int i = 0; i <= n; i++) {
                isPrime[i] = true;
            }
            for (int i = 2; i <= sqr; i++) {
                if (isPrime[i]) {
                    for (int p = i * i; p <= n; p += i) {
                        isPrime[p] = false;
                    }
                }
            }
            ArrayList<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i <= n; i++) {
                if (isPrime[i]) {
                    list.add(i);
                }
            }
            list.remove(0);
            list.remove(0);
            return list;
        }

        public static boolean isPrime(long n) {
            boolean res = true;
            List l = sieve((int) Math.sqrt(n));
            for (int i = 0; i < l.size(); i++) {
                int curPrime = (int) l.get(i);
                if (n % curPrime == 0) {
                    res = false;
                    break;
                }
            }
            return res;
        }

        public static ArrayList factorizatin(int n) {

            ArrayList<Integer> list = new ArrayList<Integer>();
            if (n == 1) {
                list.add(1);
                return list;
            } else if (n == 2) {
                list.add(2);
                return list;
            } else {
                if (isPrime(n)) {
                    System.out.println(-1);
                    return null;
                } else {
                    Iterator ptr = sieve((int) Math.sqrt(n)).iterator();
                    if (ptr.hasNext()) {
                        int cur = (int) ptr.next();
                        // System.out.println(cur);
                        while (n != 1) {
                            System.out.println(n);
                            while (n % cur == 0) {
                                list.add(cur);
                                n /= cur;
                            }
                            if (ptr.hasNext()) {
                                cur = (int) ptr.next();
                            }
                            //System.out.println(cur);
                        }
                    }
                    if (n > 2) {
                        list.add(n);
                    }
                }
                return list;
            }
        }

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

        public static long lcm(long a, long b) {
            long ab = a * b;
            long gcd = gcd(a, b);
            return ab / gcd;
        }

        public static int bs(int[] z, int k) {
            int res = 0;
            int l = 0;
            int r = z.length - 1;
            int mid = (l + r) / 2;
            while (l <= r) {

                if (z[mid] == k) {
                    res = 1;
                    break;
                }
                if (z[mid] > k) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
                mid = (l + r) / 2;
            }
            return res;
        }

        public static void solve() {
            int n = Integer.parseInt(in.next());
            int target = Integer.parseInt(in.next());
            int[] z = new int[n];
            for (int i = 0; i < n; i++) {
                z[i] = Integer.parseInt(in.next());
            }
            Arrays.sort(z);
            int ptr1 = 0;
            int ptr2 = n - 1;
            int wind = z[ptr1] + z[ptr2];
            if (wind == target) {
                System.out.println(ptr1 + "-" + ptr2);
            } else {
                while (ptr1 < ptr2 && wind != target) {
                    if (wind > target) {
                        wind -= z[ptr2--];
                        wind += z[ptr2];
                    } else {
                        wind -= z[ptr1++];
                        wind += z[ptr1];
                    }
                }
                if ((ptr1 != 0 || ptr2 != n - 1) && ptr2 != ptr1) {
                    System.out.println(ptr1 + "-" + ptr2);
                } else {
                    System.out.println(-1);
                }
            }
        }

        public static void sliding() {
            int n = Integer.parseInt(in.next());
            int k = Integer.parseInt(in.next());
            int[] z = new int[n];
            for (int i = 0; i < n; i++) {
                z[i] = Integer.parseInt(in.next());
            }
            int wind = 0;
            for (int i = 0; i < k; i++) {
                wind += z[i];
            }
            int max = wind;
            for (int i = k; i < n; i++) {
                wind += z[i];
                wind -= z[i - k];
                max = Math.max(max, wind);
            }
            System.out.println(max);
        }

        public static ArrayList<Long> dd(long n) {
            ArrayList<Long> list = new ArrayList<Long>();
            for (long i = 1; i * i <= n; i++) {
                if (n % i == 0) {
                    list.add(n / i);
                    list.add(i);
                }
            }

            return list;
        }
    }

    private static class DS {

        public static class Graph {

            int V;
            ArrayList[] data = null;
            int[] parent = null;

            public Graph(int v) {
                this.V = v + 1;
                this.data = new ArrayList[this.V];
                for (int i = 1; i < V; i++) {
                    this.data[i] = new ArrayList<Pair>();
                }
                parent = new int[v + 1];
                Arrays.fill(parent, -1);
            }

            public void add(int u, int v, int cost) {
                data[u].add(new Pair(v, cost));
                data[v].add(new Pair(u, cost));
            }

            public boolean isConnected(int u, int v) {
                if (data[u].contains(v)) {
                    return true;
                } else {
                    return false;
                }
            }

            public int[] dijkstra(int s) {
                Comparator<Pair> comp = new Comparator<Pair>() {
                    @Override
                    public int compare(Pair t, Pair t1) {
                        return (int) t.getValue() - (int) t1.getValue();
                    }

                };
                PriorityQueue<Pair> q = new PriorityQueue<>(comp);
                int[] cost = new int[this.V];
                Arrays.fill(cost, Integer.MAX_VALUE);
                q.add(new Pair(s, 0));
                cost[s] = 0;
                parent[s] = s;
                while (!q.isEmpty()) {
                    Pair cur = q.poll();
                    int u = (int) cur.getKey();
                    int cst = (int) cur.getValue();
                    ArrayList<Pair> list = data[u];
                    for (Pair p : list) {
                        int d = (int) p.getKey();
                        int curCost = (int) p.getValue();
                        if (cst + curCost <= cost[d]) {
                            parent[d] = u;
                            cost[d] = curCost + cst;
                            q.add(new Pair(d, cost[d]));
                        }
                    }
                }
                return cost;
            }
        }

        public static class Print {

            private final BufferedWriter bw;

            public Print() {
                this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
            }

            public void print(Object object) throws IOException {
                bw.append(object + "");
            }

            public void println(Object object) throws IOException {
                print(object);
                bw.append("\n");
            }

            public void close() throws IOException {
                bw.close();
            }
        }

        private static class Stack {

            private int Size;
            Node top;
            Node last;

            Stack() {

                Size = 0;
                top = null;
                last = null;
            }

            public int size() {
                return this.Size;
            }

            public void push(Object item) {
                Node node = new Node();
                node.data = item;
                node.next = top;
                top = node;
                Size++;
            }

            public void pop() {
                if (top != null) {
                    top = top.next;
                }
                Size--;
            }

            public boolean isEmpty() {
                return top == null;
            }

            public Object getTop() {
                if (top != null) {
                    return top.data;
                } else {
                    return null;
                }
            }

            public void display() {
                if (top != null) {
                    Node temp = top;
                    while (temp != null) {
                        System.out.print(temp.data + " ");
                        temp = temp.next;
                    }
                    System.out.println();
                }
            }

            private class Node {

                Object data;
                Node next;
            }
        }

        private static class Scanner {

            BufferedReader br;
            StringTokenizer st;

            public Scanner() {
                br = new BufferedReader(new InputStreamReader(System.in));
            }

            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }

            int nextInt() {
                return Integer.parseInt(next());
            }

            long nextLong() {
                return Long.parseLong(next());
            }

            double nextDouble() {
                return Double.parseDouble(next());
            }

            String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return str;
            }

            BigInteger nextBigInteger() {
                return new BigInteger(next());
            }

        }
    }

}
