#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 ans = 0; for(llint i = 0; ; i++){ ll rem = g - i * a[2]; if(rem < 0) break; P res = congruence(a[0], rem, a[1]); if(res.second == -1) continue; ll x = res.first, m = res.second, l = a[0]*a[1]/gcd(a[0], a[1]); if(x >= 1e18/a[0]) continue; //cout << x << " " << m << endl; if(rem-a[0]*x%l >= 0) ans += (rem-a[0]*x%l) / l + 1, ans %= mod; } cout << ans << endl; } return 0; }