CF1798C.Candy Store

The store sells $n$ types of candies with numbers from $1$ to $n$. One candy of type $i$ costs $b_i$ coins. In total, there are $a_i$ candies of type $i$ in the store.

You need to pack all available candies in packs, each pack should contain only one type of candies. Formally, for each type of candy $i$ you need to choose the integer $d_i$, denoting the number of type $i$ candies in one pack, so that $a_i$ is divided without remainder by $d_i$.

Then the cost of one pack of candies of type $i$ will be equal to $b_i \cdot d_i$. Let's denote this cost by $c_i$, that is, $c_i = b_i \cdot d_i$.

After packaging, packs will be placed on the shelf. Consider the cost of the packs placed on the shelf, in order $c_1, c_2, \ldots, c_n$. Price tags will be used to describe costs of the packs. One price tag can describe the cost of all packs from $l$ to $r$ inclusive if $c_l = c_{l+1} = \ldots = c_r$. Each of the packs from $1$ to $n$ must be described by at least one price tag. For example, if $c_1, \ldots, c_n = [4, 4, 2, 4, 4]$, to describe all the packs, a $3$ price tags will be enough, the first price tag describes the packs $1, 2$, the second: $3$, the third: $4, 5$.

You are given the integers $a_1, b_1, a_2, b_2, \ldots, a_n, b_n$. Your task is to choose integers $d_i$ so that $a_i$ is divisible by $d_i$ for all $i$, and the required number of price tags to describe the values of $c_1, c_2, \ldots, c_n$ is the minimum possible.

For a better understanding of the statement, look at the illustration of the first test case of the first test:

Let's repeat the meaning of the notation used in the problem:

$a_i$ — the number of candies of type $i$ available in the store.

$b_i$ — the cost of one candy of type $i$.

$d_i$ — the number of candies of type $i$ in one pack.

$c_i$ — the cost of one pack of candies of type $i$ is expressed by the formula $c_i = b_i \cdot d_i$.

商店出售 $n$ 种糖果，编号从 $1$ 到 $n$。第 $i$ 种糖果的单价为 $b_i$ 枚金币。商店中第 $i$ 种糖果共有 $a_i$ 颗。

你需要将所有现有糖果装入若干包装盒中，每个包装盒仅包含同一种类的糖果。形式化地，对每种糖果 $i$，你需要选定一个整数 $d_i$，表示每个包装盒中第 $i$ 种糖果的数量，且需满足 $d_i$ 整除 $a_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$。你的任务是为每个 $i$ 选择整数 $d_i$，使得对所有 $i$ 均有 $d_i$ 整除 $a_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$ 给出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100\,000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 200\,000$) — the number of types of candies.

Each of the next $n$ lines of each test case contains two integers $a_i$ and $b_i$ ($1 \le a_i \le 10^9$, $1 \le b_i \le 10\,000$) — the number of candies and the cost of one candy of type $i$, respectively.

It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output the minimum number of price tags required to describe the costs of all packs of candies in the store.

对于每个测试用例，输出描述商店中所有糖果包价格所需的最少价格标签数量。

In the first test case, you can choose $d_1 = 4$, $d_2 = 6$, $d_3 = 7$, $d_4 = 5$. Then the cost of packs will be equal to $[12, 12, 35, 35]$. $2$ price tags are enough to describe them, the first price tag for $c_1, c_2$ and the second price tag for $c_3, c_4$. It can be shown that with any correct choice of $d_i$, at least $2$ of the price tag will be needed to describe all the packs. Also note that this example is illustrated by a picture in the statement.

In the second test case, with $d_1 = 4$, $d_2 = 2$, $d_3 = 10$, the costs of all packs will be equal to $20$. Thus, $1$ price tag is enough to describe all the packs. Note that $a_i$ is divisible by $d_i$ for all $i$, which is necessary condition.

In the third test case, it is not difficult to understand that one price tag can be used to describe $2$nd, $3$rd and $4$th packs. And additionally a price tag for pack $1$ and pack $5$. Total: $3$ price tags.

在第一个测试用例中，你可以选择 $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$、第 $3$ 和第 $4$ 个包装；此外还需分别为第 $1$ 个和第 $5$ 个包装各分配一个价格标签。总计：$3$ 个价格标签。