← 返回题目列表

Codeforces · 1476/A

A. K-整除总和

中文机器翻译题面 查看原题

给你两个整数 $$$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$$$ 中的最小可能最大元素,使得总和 $$$(a_1 + \dots + a_n)$$$ 可被 $$$k$$$ 整除。

示例

输入 #1

4
1 5
4 3
8 8
8 17

输出 #1

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$$$。