题目其实就是让求这样一个区域的整点个数：

于是有了大体思路：先求出上面的轮廓，然后对于轮廓上的每一个线段求解答案。

求上面的轮廓方法很简单，就是先将所有直线按照斜率从大到小排序，维护一个栈，每次判断该直线与栈顶线段是否有交点，如果没有就将栈顶弹出。直到有交点时，将栈顶线段保留交点之前的部分，并将当前直线保留交点后部分加入栈。这样，最后的栈就是我们的轮廓。

注意：此过程中可能涉及平行直线，需要保留截距较小的。还有可能出现重合直线，按照我这个写法会出问题，需要判掉。

接下来对于轮廓上每个线段下方部分，求解的就是类似 P5171 的问题，差分一下，采用类欧解决即可，但是注意 $x$ 坐标在本题有限制，不要随意交换 $a,b$ 来规避负数问题。

这样我们就解决了问题，时间复杂度 $O(n\log n+n\log V)$。注意本题中如果使用浮点数运算会出现掉精度的风险，可以通过移项比大小的方式规避。

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int T,n,inf=2e18,t;
struct frac{
	int x,y;
};
struct line{
	frac l,r;
	int a,b,c;
}a[N],s[N];
bool cmp(line a,line b){
	if(a.a*b.b!=a.b*b.a)return a.a*b.b<a.b*b.a;
	return a.c*b.b>b.c*a.b;
}
int solve(int a,int b,int c,int n){
	if(!a)return (n+1)*(b/c);
	if(a>=c||b>=c)return n*(n+1)/2*(a/c)+(n+1)*(b/c)+solve(a%c,b%c,c,n);
	else{
		int m=(a*n+b)/c;
		return n*m-solve(c,c-b-1,a,m-1);
	}
}
int gzq(int a,int b,int c,int n){
	int k=(a+b-1)/b;
	return solve(k*b-a,c,b,n)-(k*n-2)*(n+1)/2; 
}
int fzj(int a,int b,int c,int l,int r){
	--c;
	return gzq(a,b,c,r)-gzq(a,b,c,l-1)-(r-l+1);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
	cin>>T;
	while(T--){
		cin>>n;t=0;
		for(int i=1;i<=n;++i)cin>>a[i].a>>a[i].b>>a[i].c;
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;++i){
			while(t>=1){
				frac l=s[t].l,r=s[t].r;
				int zi=a[i].c*s[t].b-s[t].c*a[i].b;
				int mu=a[i].a*s[t].b-s[t].a*a[i].b;
				if(!mu){
					if(a[i].c*s[t].b<s[t].c*a[i].b)--t;
                    else break;
					continue;
				}
				if(mu<0)zi=-zi,mu=-mu;
				if((__int128)l.x*mu<=(__int128)l.y*zi&&(__int128)zi*r.y<(__int128)r.x*mu){ 
					s[t+1]=a[i];s[t].r=s[t+1].l={zi,mu};
					s[t+1].r={inf,1ll};++t;
					break;
				}
				else --t;
			}
			if(!t)s[++t]={{1ll,1ll},{inf,1ll},a[i].a,a[i].b,a[i].c}; 
		}
		int ans=0;
		for(int i=1;i<=t;++i){
			int L=(s[i].l.x+s[i].l.y-1)/s[i].l.y;
			int R=min((s[i].r.x+s[i].r.y-1)/s[i].r.y-1,(s[i].c+s[i].a-1)/s[i].a-1);
			if(L<=R)ans+=fzj(s[i].a,s[i].b,s[i].c,L,R);
		}
		cout<<ans<<'\n';
	}
	return 0;
}