#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; long long gcd(long long a,long long b,long long &x,long long &y) { x = 1,y = 0; long long z = 0,w = 1; while(b) { long long q = a / b; a -= q * b; swap(a,b); x -= q * z; swap(x,z); y -= q * w; swap(y,w); } return a; } void Main() { long long a,b,c,Y; cin >> a >> b >> c >> Y; long long y,z; long long g = gcd(b,c,y,z); const int mod = (int)1e9 + 7; long long ans = 0; for(int i = 0;a * i <= Y;i++) { long long Z = Y - a * i; if(Z % g) { continue; } long long p = y * (Z / g),q = z * (Z / g); //b * p + c * q == Z q = -q; long long L = q >= 0 ? (q + b - 1) / b : -((-q) / b); long long U = p >= 0 ? p / c : -((-p + c - 1) / c); ans += max(0ll,U - L + 1); ans %= mod; } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; cin >> tt; while(tt--) Main(); }