该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

你需要构造一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots, a_n$，使其元素之和 $(a_1 + a_2 + \dots + a_n)$ 可以被 $k$ 整除，并且数组 $a$ 中的最大值尽可能小。

你的任务是：求数组 $a$ 中最大值的最小值。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

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

输出格式

对于每个测试用例，输出一个整数，表示在满足 $(a_1 + a_2 + \dots + a_n)$ 可以被 $k$ 整除的前提下，数组 $a$ 的最小可能最大值。

输入输出样例

4
1 5
4 3
8 8
8 17

5
2
1
3

说明

• 在第一个测试用例中，$n = 1$，所以数组只包含一个元素 $a_1$。如果取 $a_1 = 5$，那么它可以被 $k = 5$ 整除，并且这是最小可能值。

• 在第二个测试用例中，我们可以构造数组 $a = [1, 2, 1, 2]$，其元素之和可以被 $k = 3$ 整除，并且最大值为 $2$。

• 在第三个测试用例中，我们可以构造数组 $a = [1, 1, 1, 1, 1, 1, 1, 1]$，元素之和可以被 $k = 8$ 整除，并且最大值为 $1$。