/*** author: yuji9511 ***/ #include // #include // using namespace atcoder; using namespace std; using ll = long long; using lpair = pair; using vll = vector; const ll MOD = 1e9+7; const ll INF = 1e18; #define rep(i,m,n) for(ll i=(m);i<(n);i++) #define rrep(i,m,n) for(ll i=(m);i>=(n);i--) ostream& operator<<(ostream& os, lpair& h){ os << "(" << h.first << ", " << h.second << ")"; return os;} #define printa(x,n) for(ll i=0;i void print(H&& h, T&&... t){cout<(t)...);} ll extgcd(ll a,ll b,ll &x,ll &y){ if(b == 0){ x = 1; y = 0; return a; } ll d = extgcd(b, a % b, y, x); y -= a / b * x; return d; } void solve(){ ll A,B,C,N; cin >> A >> B >> C >> N; ll a[3]; a[0] = A; a[1] = B; a[2] = C; ll v = 1000000; if(N/A > v && N/B > v && N/C > v) exit(1); sort(a,a+3); A = a[0]; B = a[1]; C = a[2]; ll ans = 0; ll g = gcd(A,B); A /= g; B /= g; for(ll c = 0; c * C <= N; c++){ ll amari = N - c * C; // Ax + By = amari if(amari % g != 0) continue; ll x,y; extgcd(A, B, x, y); x *= amari / g; y *= amari / g; // print(A/g,B/g,amari,x,y); ll k_max = 0; if(x >= 0){ k_max = x / B; }else{ k_max = -1 * ((abs(x) + B-1) / B); } ll k_min = 0; if(y >= 0){ k_min = -1 * (y / A); }else{ k_min = (abs(y) + A-1) / A; } ll res = max(0LL, k_max - k_min + 1); ans += res; ans %= MOD; } print(ans); } int main(){ cin.tie(0); ios::sync_with_stdio(false); ll t; cin >> t; while(t--) solve(); }