龙哥有n种糖果，第i种糖果有ai块，每块bi元。对每种糖，需要选择一个整数di，要求ai能够整除di，然后每di块糖装进一个袋子。即把ai块糖果均匀装入ai/di个袋子。
现在把糖摆上货架，第i类糖的价签上的价格ci是一袋子i类糖的价值，即ci=di×bi。
对于货架上一个区间[l,r]，如果他们的价格相同，即cl=cl+1=⋯=cr ，则他们可以共用一个价格标签。
如有4种糖果，其数量分别为20、6、14、20，单价分别为3、2、5、7；则可按下图所示摆放。

现在请你帮忙计算一下，给定n种糖果的数量与单价，最少需要多少个价格标签？

第一整数为T,表示有T (1≤T≤100 000)组测试样例。
每组测试数据的第一行包含一个正整数n(2≤n≤200000)，表示糖果的种类。
接下来n行，每行2个整数ai,bi (1≤ai≤1e9,1≤bi≤10000)，分别表示每类糖果的数量与单价。
测试数据保证所有的n之和不超过200 000。

对于每组测试数据，输出一个整数，表示所需的最少价格标签数量。

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

2
1
3
2
5

在测试样例1中，可选择d1=4, d2=6, d3=7, d4=5。每袋糖果的价格分别为[12,12,35,35]。因此只需要2个价格标签（如上图所示）。
在测试样例2中，可选择 d1=4, d2=2, d3=10。每袋糖果的价格都为20。因此只需要1个价格标签。
在测试样例3中，第1种使用一个价格标签；2、3、4共用一个价格标签；第5种使用一个价格标签。因此需要3个价格标签。