You are given two integers n and k.

You should create an array of n positive integers a_1, a_2, ..., a_n such that the sum (a_1 + a_2 + ... + a_n) is divisible by k and maximum element in a is minimum possible.

What is the minimum possible maximum element in a?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first and only line of each test case contains two integers n and k (1 ≤ n ≤ 10^9; 1 ≤ k ≤ 10^9).

Output

For each test case, print one integer — the minimum possible maximum element in array a such that the sum (a_1 + ... + a_n) is divisible by k. 

Example

Input


4
1 5
4 3
8 8
8 17


Output


5
2
1
3

Note

In the first test case n = 1, so the array consists of one element a_1 and if we make a_1 = 5 it will be divisible by k = 5 and the minimum possible.

In the second test case, we can create array a = [1, 2, 1, 2]. The sum is divisible by k = 3 and the maximum is equal to 2.

In the third test case, we can create array a = [1, 1, 1, 1, 1, 1, 1, 1]. The sum is divisible by k = 8 and the maximum is equal to 1.
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

import java.util.*;		
import java.util.function.Function;
import java.util.stream.Collectors;
import java.io.*;
import java.math.*;
public class Main{
    static public void main(String args[])throws IOException{
        int tt=i();
        StringBuilder sb=new StringBuilder();
        for(int ttt=1;ttt<=tt;ttt++){
           int n=i();
           int k=i();
           if (n > k) {
               if (n%k==0) {
                   sb.append("1\n");
               } else {
               sb.append("2\n");
              }
           } else if(n == k) {
               sb.append("1\n");
           } else {
               int num = (k-n)/n;
               if((k-n)%n!=0) {
                   num++;
               }
               sb.append((num+1)+"\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{
        int x;
        int y;
        int z;
        Pair(int 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)%mod;
                b--;
            } 
            a=(a*a)%mod;
            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();
    }
 }
class IOUtils {
    public static int[] readIntArray(InputReader in, int size) {
        int[] array = new int[size];
        for (int i = 0; i < size; i++)
                array[i] = in.Int();
        return array;
    }
} 
