题目链接：https://codeforces.com/contest/1798/problem/C
大致题意：给你一个长度为\(n(n<=2e5)\)的序列的\(a_i,b_i\)，让你把这个序列分成数目最少的段，每一段都有一个值\(c\)，\(c=a_i的一个约数乘以b_i\)。
比赛没写出的题。
思路：\(首先一段里面的所有a_i*b_i能够整除c，易得c是所有b的最小公倍数(这个是满足条件的最小值，条件最不苛刻。)，则这一段所有a*b的最大公约数能够整除lcm(b_i)即可。\)
一个小结论的证明：
反证法：不如就设两个数\(x,y\)，\(g = gcd(x,y)\)，\(z\)同时可以被这两个数整除，但\(g\)不能整除\(z\)，
则\(lcm(g,z)\)一定大于\(g\)，但这个数也可以同时被\(x,y\)整除，所以\(g\)不可能为\(x,y\)的最大公约数。得证。
结论：如果某一段数都同时可以整除以某一个数，则这一段的最大公约数也一定可以整除以这一个数。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int A[N],B[N];
long long gcd(long long x,long long y){
if (!y) return x;
else return gcd(y,x%y);
}
long long lcm(long long x,long long y){
return x*y/gcd(x,y);
}
void solve(){
int n;
cin>>n;
for (int i=1;i<=n;i++) cin>>A[i]>>B[i];
int ans = 1;
long long g = 0,l = 1;
for (int i=1;i<=n;i++){
if (gcd(g,1ll*A[i]*B[i])%lcm(l,B[i])!=0){
g = A[i]*1ll*B[i],l = B[i];
ans++;
}
else{
g = gcd(g,1ll*A[i]*B[i]);
l = lcm(l,B[i]);
}
}
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
cin>>T;
while(T--) solve();
return 0;
}