def f(a, b): """ ax + by = gcd(a,b) = d となる (x,y,d) を返す """ if b == 0: return (1, 0, a) q, r = a // b, a % b x, y, d = f(b, r) s, t = y, x - q * y return s, t, d #================================================ from math import gcd T=int(input()) assert 1<=T<=10,"Tが制約違反(T={})".format(T) for _ in range(T): N,K,H,Y=map(int,input().split()) assert 1<=N<=10**6,"Nが制約違反(N={})".format(N) assert 1<=K<=10**6,"Kが制約違反(N={})".format(K) assert 1<=H<=10**6,"Hが制約違反(N={})".format(H) assert 1<=Y<=10**12,"Yが制約違反(Y={})".format(Y) assert min(Y//N,Y//K,Y//H)<=10**6,"計算量が多すぎ(N={},K={},H={},Y={})".format(N,K,H,Y) N,K,H=sorted([N,K,H],reverse=True) Mod=10**9+7 Ans=0 g=gcd(K,H) A,B=K//g,H//g p,q,_=f(A,B) for x in range(0,Y//N+1): beta=Y-N*x if beta%g: continue S=beta//g upper=S*q//A lower=(-S*p+(B-1))//B Ans+=upper-lower+1 Ans%=Mod print(Ans)