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.
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class A {

	static void pr(int i) {
		System.out.println(i);
	}

	static void pr(int[] ar) {
		for (int i : ar) {
			System.out.print(i + " ");
		}
		System.out.println("");
	}

	static int max(int[] ar) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < ar.length; i++) {
			max = ar[i] > ar[max] ? i : max;
		}
		return max;
	}

	static int max(long[] ar) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < ar.length; i++) {
			max = ar[i] > ar[max] ? i : max;
		}
		return max;
	}

	static int max(List<Integer> ar) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < ar.size(); i++) {
			max = ar.get(i) > ar.get(max) ? i : max;
		}
		return max;
	}

	static int kgv(int a, int b) {
		int ret = 0;
		outer: for (int i = 1; i <= b; i++) {
			for (int j = 1; j <= a; j++) {
				if (b * j > a * i)
					break;
				if (b * j == a * i) {
					ret = a * i;
					break outer;
				}
			}
		}
		return ret;
	}

	static int binarySearch(List<Integer> ar, int x, int l, int r) {
		if (l <= r) {
			int mid = l + (r - l) / 2;

			if (ar.get(mid) == x)
				return mid;

			if (ar.get(mid) > x)
				return binarySearch(ar, x, l, mid - 1);
			else
				return binarySearch(ar, x, mid + 1, r);
		}

		return -1;
	}

	static int binarySearch(int[] ar, int x, int l, int r) {
		if (l <= r) {
			int mid = l + (r - l) / 2;

			if (ar[mid] == x)
				return mid;

			if (ar[mid] > x)
				return binarySearch(ar, x, l, mid - 1);
			else
				return binarySearch(ar, x, mid + 1, r);
		}

		return -1;
	}

	static int testCase(int n, int k) {
		int ret = 0;
		
		int d = (int) Math.ceil((double) n/k);
		d *= k;
		
		ret = (int) Math.ceil(d/(double)n);
		
		return ret;
	}

	public static void main(String[] args) throws IOException {
		Reader sc = new Reader(System.in);
		int t = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		while(t-- > 0) {
			int n, k;
			n = sc.nextInt();
			k = sc.nextInt();
			sb.append(testCase(n, k)).append("\n");
		}
		System.out.println(sb);
		sc.close();
	}

	protected static class Reader {
		private final int BUFFER_SIZE = 1 << 16;
		private final DataInputStream din;
		private final byte[] buffer;
		private int bufferPointer, bytesRead;
		private final int al = 1024;

		public Reader(InputStream din) {
			this.din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String next() throws IOException {
			byte[] buf = new byte[al];
			int cnt = 0, c = 0;
			while ((c = read()) != -1) {
				if (c == ' ')
					break;
				if (c == '\n') {
					cnt--;
					break;
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt == -1 ? 0 : cnt);
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[al]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					cnt--;
					break;
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt == -1 ? 0 : cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

}
