#include using namespace std; #define ll long long #define lll long long//__int128 #define pii pair //#define f first #define s second # define pi 3.14159265358979323846 #include using namespace __gnu_pbds; struct chash_key { ll operator()(pii x) const { return (ll)x.first*1000000000 + x.second; } }; //gp_hash_table hs[2],p[2]; //gp_hash_table dp; /* ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); cout << fixed; cout.precision(3); cout << x << '\n'; */ struct P { int x,y,z; bool operator <(const P &a)const { return y>a.y; }; }; int a,b,c; const ll mod=998244353; //sum (ai+b)/c for i=0 to n long long FloorSumAP(long long a, long long b, long long c, long long n){ //cout<= c or b >= c) return ( ( n * (n + 1) ) / 2) * (a / c) + (n + 1) * (b / c) + FloorSumAP(a % c, b % c, c, n); long long m = (a * n + b) / c; return m * n - FloorSumAP(c, c - b - 1, a, m - 1); } int main() { ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); int ttt=100; cin>>ttt; a=3,b=4; for(int tt=1;tt<=ttt;tt++) { c=tt; cin>>a>>b>>c; ll x=1,y=(ll)a*c; int g=__gcd(a,b); ll L=(ll)a*b/g; for(;x