fn main() -> std::io::Result<()> {
    use std::io::Write;
    let mut bw = std::io::BufWriter::new(std::io::stdout());
    input! { t: usize }
    for _ in 0..t {
        input! { n: i64, m: i64, a: i64, b: i64, c: i64, d: i64 }
        assert!(n > 0 && m > 0 && 0 <= c && c < m && 0 <= d && d < m);
        let ans = mwf(n, m, a, b, c, d);
        writeln!(bw, "{}", ans)?;
    }
    bw.flush()?;
    Ok(())
}

fn mwf(mut n: i64, mut m: i64, mut a: i64, mut b: i64, mut c: i64, mut d: i64) -> i64 {
    assert!(n > 0 && m > 0);
    let (mut sum_acc, mut max_acc) = (0, d.div_euclid(m) * b);
    loop {
        let q;
        (q, c) = (c.div_euclid(m), c.rem_euclid(m));
        a += b * q;
        let q;
        (q, d) = (d.div_euclid(m), d.rem_euclid(m));
        sum_acc += b * q;
        max_acc = max_acc.max(sum_acc);
        let n1 = n - 1;
        let y_max = (c * n1 + d) / m;
        if y_max == 0 {
            return max_acc.max(sum_acc + a * n1);
        }
        if a >= 0 {
            max_acc = max_acc.max(sum_acc + a * n1 + b * y_max);
            if b >= 0 {
            	return max_acc;
            }
        } else {
        	if b <= 0 {
        		return max_acc;
        	}
            sum_acc += a + b;
        }
        n = y_max;
        d = m - d - 1;
        std::mem::swap(&mut a, &mut b);
        std::mem::swap(&mut c, &mut m);
    }
}

use input_lite::*;
#[rustfmt::skip]#[allow(unused)]mod input_lite{#[macro_export]macro_rules!read_value{($b:expr,($($t:tt),*))=>{($(read_value!($b,$t)),*)};($b:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($b,$t)).collect::<Vec<_>>()};($b:expr,byte)=>{token($b,|s|s[0])};($b:expr,Bytes)=>{token($b,|s|s.to_vec())};($b:expr,Chars)=>{token($b,|s|std::str::from_utf8(s).unwrap().chars().collect::<Vec<_>>())};($b:expr,usize1)=>{read_value!($b,usize)-1};($b:expr,$t:ty)=>{token($b,|s|std::str::from_utf8(s).unwrap().parse::<$t>().unwrap())};}#[macro_export]macro_rules!input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}#[macro_export]macro_rules!input{(source=$s:expr,$($r:tt)*)=>{input_inner!{$s,$($r)*}};($($r:tt)*)=>{let mut i=std::io::stdin().lock();input_inner!{&mut i,$($r)*}std::mem::drop(i);};}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->T)->T{let(b,mut l)=loop{let b=r.fill_buf().unwrap();assert!(!b.is_empty());if let Some(p)=b.iter().position(|&b|!b.is_ascii_whitespace()){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){let t=&b[..p];let x=f(t);r.consume(l+p+1);return x;}l+=b.len();let mut t=b.to_vec();r.consume(l);while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}f(&t)}}