#include <bits/stdc++.h>

using namespace std;
typedef __int128 ll;

constexpr ll INF = 1e36;

// ll floordiv(ll x, ll y) {
//     return x >= 0 ? x/y : -((-x)/y);
// }

ll solve(ll N, ll M, ll A, ll B, ll C, ll D) {
    // cout << N << " " << M << " " << A << " " << B << " " << C << " " << D << '\n';
    ll at_zero = B*(D/M);
    if (N <= 0) return -INF;
    if (N == 1) return at_zero;
    
    if (C == 0 || M == 1) {
        return max(at_zero, A*(N-1) + B*((C*(N-1) + D)/M));
    }
    
    if (A < 0) {
        // left endpoint
        ll nxt_N = (C*(N-1)+D)/M - D/M;
        
        if (nxt_N == 0) {
            return at_zero;
        }
        
        // cout << -A*additional << "\n";
        
        return max(
            at_zero,
            B*(D/M + 1) + solve(nxt_N, C, B, A, M, M*(D/M + 1) - D + C - 1)
        );
    } else {
        // right endpoint
        ll nxt_N = (C*(N-1)+D)/M;
        ll nxt_M = C;
        ll nxt_C = M;
        ll nxt_D = M-D-1;
        ll additional = 0;
        
        if (nxt_D < 0) {
            additional = (-nxt_D)/nxt_M + 1;
            nxt_D += additional*nxt_M;
        } else {
            additional = nxt_D/nxt_M;
            nxt_D -= nxt_M*additional;
            additional = -additional;
        }
        
        // cout << -A*additional << "\n";
        
        return max(
            A*(N-1) + B*((C*(N-1) + D) / M),
            solve(nxt_N, nxt_M, B + A*(nxt_C/nxt_M), A, nxt_C%nxt_M, nxt_D) - A*additional
        );
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T;
    
    while (T--) {
        long long N, M, A, B, C, D;
        cin >> N >> M >> A >> B >> C >> D;
        cout << (long long)solve(N, M, A, B, C, D) << "\n";
        // cout << "===\n";
    }
    
    return 0;
}