#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define all(x) (x).begin(),(x).end() #define inf 1e18 #define mod 1000000007 using namespace std; typedef long long llint; typedef long long ll; typedef pair P; llint gcd(llint a, llint b) { if(b == 0) return a; return gcd(b, a%b); } //ax+by = gcd(a, b)を満たす(x, y)を求めgcd(a, b)を返す llint extgcd(llint a, llint b, llint &x, llint &y) { if(b == 0){ x = 1, y = 0; return a; } llint xx, yy; llint d = extgcd(b, a%b, xx, yy); x = yy, y = xx-(a/b)*yy; return d; } //a^{-1} (mod m)を求める。存在しない場合(gcd(a, m)!=1)は-1を返す llint mod_inverse(llint a, llint m) { llint x, y; if(extgcd(a, m, x, y) != 1) return -1; return (x%m + m) % m; } //ax = b (mod m)を満たすx(mod m/gcd(a, m))を求める。存在しない場合(b%gcd(a, m)!=0)は(0, -1)を返す P congruence(llint a, llint b, llint m) { llint d = gcd(a, m); if(b % d) return make_pair(0, -1); a /= d, b /= d, m /= d; return make_pair(b * mod_inverse(a, m) % m, m); } ll T; ll a[3], g; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> T; while(T--){ cin >> a[0] >> a[1] >> a[2] >> g; sort(a, a+3); ll A = a[0], B = a[1]; ll d = gcd(A, B), l = A*B/d; ll inv = mod_inverse(A/d, B/d) % (B/d); ll ans = 0; for(llint i = 0; ; i++){ ll rem = g - i * a[2]; if(rem < 0) break; if(rem % d) continue; ll x = (rem/d) % (B/d) * inv % (B/d); if(x >= 1e18/A) continue; //cout << x << " " << m << endl; if(rem-A*x%l >= 0){ ans += (rem-A*x%l) / l + 1; if(ans >= mod) ans -= mod; } } cout << ans << endl; } return 0; }