题目描述

给定两个整数 $n$ 和 $k$。

你需要构造一个长度为 $n$ 的 正整数数列 $a_1, a_2, \ldots, a_n$，要求：在数列中的每个元素均为正整数且数列和（即：$(a_1 + a_2 + \ldots + a_n)$）是 $k$ 的倍数的情况下，数列元素的最大值尽可能地小。

求：能够构造的所有满足条件的数列中，最大值最小是多少？

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 $t(1 \le t \le 1000)$，表示测试数据组数。

接下来，每组测试数据包含一行，包含两个整数 $n$ 和 $k$（$1 \le n, k \le 10^9$）。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示构造一个长度为 $n$ 且数列和为 $k$ 的倍数的正整数数列的情况下数列中的最大值最小是多少。

input

4
1 5
4 3
8 8
8 17

output

5
2
1
3

说明/提示

样例解释

第1组测试数据，最优方案是令 $a_1 = 5$，此时数列的最大值为 $5$。

第2组测试数据，一种最优方案是 $a = [1, 2, 1, 2]$，此时数列的最大值为 $2$。

第3组测试数据，最优方案是 $a = [1, 1, 1, 1, 1, 1, 1, 1]$，此时数列的最大值为 $1$。

第4组测试数据，一种最优方案是 $a = [2, 2, 2, 2, 2, 2, 2, 3]$，此时数列的最大值为 $3$。

数据规模与约定

• 对于 $30\%$ 的数据，$t \le 10; n,k \le 1000$
• 对于 $60\%$ 的数据，$t \le 100; n,k \le 10^6$
• 对于 $100\%$ 的数据，$1 \le t \le 1000; 1 \le n,k \le 10^9$