题目描述

给定两个整数 $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$ 的最大元素的最小可能值。

说明/提示

在第一个测试用例中，$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$。

由 ChatGPT 4.1 翻译

样例

4
1 5
4 3
8 8
8 17

5
2
1
3