商店出售$$$n$$$种糖果,编号从$$$1$$$到$$$n$$$。一颗 $$$i$$$ 类型的糖果需要花费 $$$b_i$$$ 硬币。商店中总共有 $$$a_i$$$ 类型的糖果 $$$i$$$。
您需要将所有可用的糖果打包,每个包只能包含一种类型的糖果。形式上,对于每种类型的糖果 $$$i$$$,您需要选择整数 $$$d_i$$$,表示一包中 $$$i$$$ 类型糖果的数量,以便 $$$a_i$$$ 除以 $$$d_i$$$ 没有余数。
那么一包 $$$i$$$ 类型的糖果的成本将等于 $$$b_i \cdot d_i$$$。我们用 $$$c_i$$$ 来表示这个成本,即 $$$c_i = b_i \cdot d_i$$$。
包装后,包装将被放置在货架上。考虑放置在货架上的包装的成本,按顺序 $$$c_1、c_2、\ldots、c_n$$$。价格标签将用于描述包装的成本。如果 $$$c_l = c_{l+1} = \ldots = c_r$$$,则一个价格标签可以描述从 $$$l$$$ 到 $$$r$$$ 的所有包的成本。从 $$$1$$$ 到 $$$n$$$ 的每一包必须至少用一个价格标签来描述。例如,如果 $$$c_1, \ldots, c_n = [4, 4, 2, 4, 4]$$$,要描述所有包装,$$$3$$$ 价格标签就足够了,第一个价格标签描述包装 $$$1, 2$$$,第二个:$$$3$$$,第三个:$$$4, 5$$$。
给定整数 $$$a_1, b_1, a_2, b_2, \ldots, a_n, b_n$$$。您的任务是选择整数 $$$d_i$$$,使得所有 $$$i$$$ 的 $$$a_i$$$ 都能被 $$$d_i$$$ 整除,并且描述 $$$c_1, c_2, \ldots, c_n$$$ 的值所需的价格标签数量是尽可能的最小值。
为了更好地理解该语句,请看第一个测试的第一个测试用例的图示:
让我们重复一下问题中使用的符号的含义:
$$$a_i$$$ — 商店中可用的 $$$i$$$ 类型糖果的数量。
$$$b_i$$$ — 一颗 $$$i$$$ 类型糖果的成本。
$$$d_i$$$ — 一包中 $$$i$$$ 类型糖果的数量。
$$$c_i$$$ — 一包 $$$i$$$ 类型糖果的成本由公式 $$$c_i = b_i \cdot d_i$$$ 表示。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200\,000$$$) — 糖果类型的数量。
每个测试用例接下来的 $$$n$$$ 行都包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$1 \le b_i \le 10\,000$$$) - 糖果的数量和一颗糖果类型的成本分别是$$$i$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。
输出
对于每个测试用例,输出描述商店中所有包糖果的成本所需的最少价格标签数量。
示例
输入 #1
5 4 20 3 6 2 14 5 20 7 3 444 5 2002 10 2020 2 5 7 7 6 5 15 2 10 3 7 7 5 10 1 11 5 5 1 2 2 8 2 6 7 12 12 3 5 3 9 12 9 3 1000000000 10000
输出 #1
2 1 3 2 5
注意
在第一个测试用例中,您可以选择 $$$d_1 = 4$$$、$$$d_2 = 6$$$、$$$d_3 = 7$$$、$$$d_4 = 5$$$。那么包的成本将等于 $$$[12, 12, 35, 35]$$$。 $$$2$$$ 价格标签足以描述它们,第一个价格标签为$$$c_1、c_2$$$,第二个价格标签为$$$c_3、c_4$$$。可以证明,只要 $$$d_i$$$ 的任何正确选择,至少需要 $$$2$$$ 的价格标签来描述所有包装。另请注意,该示例是通过声明中的图片进行说明的。
在第二个测试用例中,$$$d_1 = 4$$$、$$$d_2 = 2$$$、$$$d_3 = 10$$$,所有包的成本将等于 $$$20$$$。因此,$$$1$$$ 价格标签足以描述所有包。请注意,对于所有 $$$i$$$,$$$a_i$$$ 可以被 $$$d_i$$$ 整除,这是必要条件。
在第三个测试用例中,不难理解,一个价格标签可以用来描述第 $$$2$$$nd、$$$3$$$rd 和 $$$4$$$th 包。另外还有包装 $$$1$$$ 和包装 $$$5$$$ 的价格标签。总计:$$$3$$$ 价格标签。