#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=200005;
const __int128 B=1000000000000000000;
struct BigInt{
    vector<ll> v; bool sgn;
    BigInt(){v.clear(); sgn=0;}
    BigInt(long long n){if(n<0) sgn=1,n=-n; else sgn=0; if(n==0) v.push_back(0); while(n>0){v.push_back(n%B); n/=B;}}
    BigInt(__int128 n){if(n<0) sgn=1,n=-n; else sgn=0; if(n==0) v.push_back(0); while(n>0){v.push_back((ll)(n%B)); n/=B;}}
    bool operator<(const BigInt& o)const{if(sgn!=o.sgn) return sgn; if(v.size()!=o.v.size()) return sgn?(v.size()>o.v.size()):(v.size()<o.v.size()); for(int i=v.size()-1;i>=0;i--) if(v[i]!=o.v[i]) return sgn?(v[i]>o.v[i]):(v[i]<o.v[i]); return 0;}
    bool operator>(const BigInt& o)const{return o<*this;}
    bool operator<=(const BigInt& o)const{return not(*this>o);}
    bool operator>=(const BigInt& o)const{return not(*this<o);}
    bool operator==(const BigInt& o)const{return sgn==o.sgn and v==o.v;}
    BigInt operator+(const BigInt& o)const{
        BigInt r; r.sgn=sgn;
        if(sgn==o.sgn){
            __int128 c=0;
            for(size_t i=0;i<max(v.size(),o.v.size()) or c;i++){
                __int128 val=c+(i<v.size()?v[i]:0)+(i<o.v.size()?o.v[i]:0);
                r.v.push_back((ll)(val%B)); c=val/B;
            }
        }else{
            if((*this).abs()<o.abs()){r=o+(*this); return r;}
            __int128 c=0;
            for(size_t i=0;i<v.size();i++){
                __int128 val=(__int128)v[i]-(i<o.v.size()?o.v[i]:0)-c;
                if(val<0){val+=B; c=1;} else c=0;
                r.v.push_back((ll)val);
            }
            while(r.v.size()>1 and r.v.back()==0) r.v.pop_back();
            if(r.v.size()==1 and r.v[0]==0) r.sgn=0;
        }
        return r;
    }
    BigInt operator-(const BigInt& o)const{BigInt t=o; t.sgn=not t.sgn; return *this+t;}
    BigInt operator*(__int128 n)const{
        BigInt r; if(n==0){r.v.push_back(0); return r;}
        r.sgn=sgn^(n<0); n=n<0?-n:n; __int128 c=0;
        for(size_t i=0;i<v.size() or c;i++){
            __int128 val=c+(i<v.size()?(__int128)v[i]*n:0);
            r.v.push_back((ll)(val%B)); c=val/B;
        }
        return r;
    }
    BigInt abs()const{BigInt r=*this; r.sgn=0; return r;}
    void print(){if(sgn and not(v.size()==1 and v[0]==0)) printf("-"); printf("%lld",v.back()); for(int i=(int)v.size()-2;i>=0;i--) printf("%018lld",v[i]); printf("\n");}
};
BigInt operator*(__int128 n, const BigInt& b){return b*n;}
BigInt div_floor(BigInt a, __int128 b){
    BigInt q; __int128 r=0; bool qs=a.sgn^(b<0); b=b<0?-b:b;
    for(int i=(int)a.v.size()-1;i>=0;i--){
        __int128 val=r*B+a.v[i];
        if(q.v.size() or val/b) q.v.push_back((ll)(val/b));
        r=val%b;
    }
    reverse(q.v.begin(),q.v.end());
    if(q.v.empty()) q.v.push_back(0);
    q.sgn=qs;
    if(q.v.size()==1 and q.v[0]==0) q.sgn=0;
    if(a.sgn and r!=0) return q-BigInt((ll)1);
    return q;
}
BigInt max_bi(BigInt a, BigInt b){return a<b?b:a;}
BigInt solve1(__int128 a, BigInt b, __int128 c, __int128 d, BigInt e, __int128 f, BigInt k, BigInt L);
BigInt solve2(__int128 a, __int128 b, BigInt c, __int128 d, __int128 e, BigInt k, BigInt L){
    if(a==0){
        BigInt rhs=div_floor(k*(-1),e);
        if(L<rhs or L==rhs) return L;
        return BigInt((ll)-1);
    }
    BigInt t1=div_floor(L*b+c,d), t2=div_floor(L*e+k+BigInt(a-1),a);
    BigInt y_min=max_bi(t1,t2);
    BigInt Y=solve1(a,k*(-1),e,d,c*(-1)+BigInt(b-1),b,BigInt((ll)0),y_min);
    if(Y.sgn and Y.v.back()==1 and Y.v.size()==1) return BigInt((ll)-1);
    return max_bi(L,div_floor(Y*d-c+BigInt(b-1),b));
}
BigInt solve1(__int128 a, BigInt b, __int128 c, __int128 d, BigInt e, __int128 f, BigInt k, BigInt L){
    if(L.sgn) L=BigInt((ll)0);
    if(div_floor(L*a+b,c)-div_floor(L*d+e,f)>=k) return L;
    __int128 q1=a/c, r1=a%c, q2=d/f, r2=d%f, alpha=q1-q2;
    if(alpha>0){
        BigInt cur=div_floor(L*a+b,c)-div_floor(L*d+e,f);
        BigInt add=div_floor(k-cur+BigInt(alpha-1),alpha)+BigInt((ll)2);
        BigInt low=L, high=L+add, mid, ans=BigInt((ll)-1);
        while(low<high or low==high){
            mid=div_floor(low+high,2);
            if(mid<L) {low=L; continue;}
            if(div_floor(mid*a+b,c)-div_floor(mid*d+e,f)>=k) ans=mid, high=mid-BigInt((ll)1);
            else low=mid+BigInt((ll)1);
            if(low>high) break;
        }
        return ans;
    }else if(alpha<0) return BigInt((ll)-1);
    else{
        BigInt u_min=div_floor(L*r2+e,f);
        BigInt res=solve2(r2,c,k*c-b+BigInt(r1-1),r1,f,e*(-1),u_min);
        if(res.sgn and res.v.back()==1 and res.v.size()==1) return BigInt((ll)-1);
        return max_bi(L,div_floor((res+k)*c-b+BigInt(r1-1),r1));
    }
}
int main(){
    int t; scanf("%d",&t);
    while(t--){
        ll D_in, A_in, B_in, K_in; scanf("%lld%lld%lld%lld",&D_in,&A_in,&B_in,&K_in);
        __int128 D=D_in, A=A_in, B_val=B_in, K=K_in;
        __int128 C=(A*B_val)/D;
        BigInt q=solve1(A,BigInt(A-1),D,C,BigInt((ll)0),B_val,BigInt(K+1),BigInt((ll)0));
        if(q.sgn and q.v.back()==1 and q.v.size()==1) printf("-1\n");
        else{
            BigInt rhs=div_floor(q*C,B_val)+BigInt(K+1);
            BigInt r_min=rhs*D-q*A;
            if(r_min.sgn) r_min=BigInt((ll)0);
            (q*A+r_min).print();
        }
    }
    return 0;
}