// -*- coding:utf-8-unix -*-
fn mwf(l: i64, r: i64, mut m: i64, mut a: i64, mut b: i64, mut c: i64, mut d: i64) -> i64 {
    assert!(l < r && 0 < m);
    let mut n = r - l;
    let (qc, qd);
    (qc, c) = (c.div_euclid(m), c.rem_euclid(m));
    a += b * qc;
    (qd, d) = (d.div_euclid(m), d.rem_euclid(m));
    let mut sum_acc = a * l + b * qd;
    let mut max_acc = sum_acc;
    loop {
        n -= 1;
        invariant!(0 < m);
        let y_max = (c * n + d) / m;
        max_acc.chmax(sum_acc);
        max_acc.chmax(sum_acc + a * n + b * y_max);
        if (a <= 0 && b <= 0) || (a >= 0 && b >= 0) || y_max == 0 {
            return max_acc;
        }
        if a < 0 {
            sum_acc += a + b;
        }
        n = y_max;
        d = m + !d;
        std::mem::swap(&mut a, &mut b);
        std::mem::swap(&mut c, &mut m);
        invariant!(0 < m);
        let (qc, qd);
        (qc, c) = (c / m, c % m);
        a += b * qc;
        (qd, d) = (d / m, d % m);
        sum_acc += b * qd;
    }
}

pub fn solve<B: std::io::BufRead>(mut input: B) -> std::io::Result<()> {
    let mut bw = FBufWriter::new(std::io::stdout().lock());

    input! { source = &mut input,
        t: usize,
    }
    for _ in 0..t {
        input! { source = &mut input,
            n: i64, m: i64, a: i64, b: i64, c: i64, d: i64,
        }
        bw.i_ln(mwf(0, n, m, a, b, c, d))?;
    }
    bw.flush()?;
    Ok(())
}

use __cargo_equip::crates::{change::*, input_lite3::*, invariant::*, fastout::*};

#[rustfmt::skip]pub fn main()->std::io::Result<()>{#[cfg(target_os="linux")]pub fn launch()->std::io::Result<()>{use std::os::unix::io::FromRawFd;#[link(name="c")]extern "C"{fn mmap(addr:*mut u8,length:usize,prot:i32,flags:i32,fd:i32,off:isize)->*mut u8;}match unsafe{std::fs::File::from_raw_fd(0)}.metadata(){Ok(metadata) if metadata.is_file()=>{let filelen=metadata.len();let input=unsafe{mmap(std::ptr::null_mut(),filelen as usize,1,2,0,0)};solve(unsafe{std::slice::from_raw_parts(input,filelen as usize)})}_=>solve(std::io::stdin().lock())}}#[cfg(not(target_os="linux"))]pub fn launch()->std::io::Result<()>{solve(std::io::stdin().lock())}const USE_THREAD:bool=false;if USE_THREAD{let stack_size=134_217_728;let thd=std::thread::Builder::new().stack_size(stack_size);thd.spawn(||launch()).unwrap().join().unwrap()}else{launch()}}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `mizar-competitive-integer-minmod 0.0.0 (path+████████████████████████████████████████████████████████████████████████████)` published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::minmod`
///  - `mizar-competitive-io-fastout 0.0.0 (path+████████████████████████████████████████████████████████████████████████)`         published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::fastout`
///  - `mizar-competitive-io-input-lite3 0.0.0 (path+████████████████████████████████████████████████████████████████████████████)` published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::input_lite3`
///  - `mizar-competitive-misc-change 0.0.0 (path+█████████████████████████████████████████████████████████████████████████)`       published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::change`
///  - `mizar-competitive-misc-invariant 0.0.0 (path+████████████████████████████████████████████████████████████████████████████)` published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::invariant`
///  - `mizar-competitive-misc-primint 0.0.0 (path+██████████████████████████████████████████████████████████████████████████)`     published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__mizar_competitive_misc_primint_0_0_0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod minmod {use crate::__cargo_equip::preludes::minmod::*;use crate::__cargo_equip::crates::invariant::*;pub fn minmod(n:u32,m:u32,a:u32,b:u32)->u32{debug_assert!(0<n&&0<m&&a<m&&b<m);let(mut r,mut s,mut n,mut m,mut a,mut b,mut c,mut d)=(i64::MAX,b as i64,(n as i64)-1,m as i64,a as i64,-(m as i64),a as i64,b as i64,);loop{invariant!(0<m&&0<=(c*n+d));let y=(c*n+d)/m;r=r.min(s+(a*n+b*y).min(0));if y==0{return r as u32;}s+=if a>0{a+b}else{0};(n,d)=(y-1,m+!d);(a,b)=(b,a);(c,m)=(m,c);invariant!(0<m&&0<c&&m<c&&0<=d);let(qc,qd);(qc,c)=(c/m,c%m);a+=qc*b;(qd,d)=(d/m,d%m);s+=qd*b;}}}
        pub mod fastout {use std::*;pub use io::Write;use ptr::copy_nonoverlapping as c;type R=io::Result<()>;type P=*mut u8;const O4:u64=10000;const O8:u64=O4*O4;const O16:u64=O8*O8;const H32:u128=10u128.pow(32);macro_rules!invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){unsafe{hint::unreachable_unchecked()}}};}const LP:[u32;10000]={let(mut x,mut i)=([0u32;10000],0);while i<10000{let(a,b,c,d)=(i/1000,i/100%10,i/10%10,i%10);x[i as usize]=0x30303030|a|(b<<8)|(c<<16)|(d<<24);i+=1;}x};const LS:[u32;10000]={let(mut x,mut i)=([0u32;10000],0);while i<10000{let(a,b,c,d)=(i/1000,i/100%10,i/10%10,i%10);x[i as usize]=match i{0..=9=>0x30|d,10..=99=>0x3030|c|(d<<8),100..=999=>0x303030|b|(c<<8)|(d<<16),_=>0x30303030|a|(b<<8)|(c<<16)|(d<<24),};i+=1;}x};#[inline]unsafe fn d4(v:&mut P,x:u64){invariant!(x<O4);c(LP[x as usize].to_le_bytes().as_ptr(),*v,4);*v=v.add(4)}#[inline]unsafe fn d4l(v:&mut P,x:u64){invariant!(x<O4);c(LS[x as usize].to_le_bytes().as_ptr(),*v,4);*v=v.add(1+(x>9)as usize+(x>99)as usize+(x>999)as usize);}#[inline]unsafe fn d8(v:&mut P,x:u64){invariant!(x<O8);let(y0,y1)=drq4(x);d4(v,y0);d4(v,y1)}#[inline]unsafe fn d16(v:&mut P,x:u64){invariant!(x<O16);let(y0,y1)=dro8(x);d8(v,y0);d8(v,y1)}#[inline]unsafe fn d8l(v:&mut P,x:u64){invariant!(x<O8);if x<O4{d4l(v,x)}else{let(y0,y1)=drq4(x as _);d4l(v,y0);d4(v,y1)}}#[inline]unsafe fn d16l(v:&mut P,x:u64){invariant!(x<O16);if x<O8{d8l(v,x)}else{let(y0,y1)=dro8(x);d8l(v,y0);d8(v,y1)}}#[inline]pub unsafe fn du8(v:&mut P,x:u8){d4l(v,x as _)}#[inline]pub unsafe fn du16(v:&mut P,x:u16){d8l(v,x as _)}#[inline]pub unsafe fn du32(v:&mut P,x:u32){if x<O8 as _{d8l(v,x as _)}else{let(y0,y1)=drq8(x as _);invariant!(y0<43);d4l(v,y0);d8(v,y1)}}#[inline]pub unsafe fn du64(v:&mut P,x:u64){if x<O16{d16l(v,x)}else{let(y0,y1)=dro16(x);invariant!(y0<1845);d4l(v,y0);d16(v,y1)}}#[inline]pub unsafe fn dusize(v:&mut P,x:usize){du64(v,u64::try_from(x).unwrap())}#[inline]fn drh_16(x:u128)->(u64,u64){invariant!(x<0xd8e03efa8ff0175cfffffffff0000);let q=((((x>>52)as u64)as u128*8307674973655724205)>>64)as u64;let r=(x as u64).wrapping_sub(q.wrapping_mul(O16));if let Some(s)=r.checked_sub(O16){(q+1,s)}else{(q,r)}}const O19:u64=1000*O16;const H19:u128=O19 as _;#[inline]unsafe fn d3(v:&mut P,x:u64){invariant!(x<1000);c((LP[x as usize]>>8).to_le_bytes().as_ptr(),*v,4);*v=v.add(3);}#[inline]unsafe fn d19(v:&mut P,x:u64){invariant!(x<O19);let(y0,y1)=dro16(x);d3(v,y0);d16(v,y1);}#[inline]fn drh19(x:u128)->(u64,u64){invariant!(x>>64<H19);let q=((x>>64)*17014118346046923173>>64)as u64;let r=((x>>19)as u64).wrapping_sub(q.wrapping_mul(O19>>18));let s=(r as u128*519229685853483>>93)as u64;(q*2+s,(x as u64&0x7ffff)|(r<<19).wrapping_sub(O19*s))}#[inline]fn dro16(x:u64)->(u64,u64){let q=(x as u128*4153837486827862103>>115)as u64;(q,x-q*O16)}#[inline]fn dro8(x:u64)->(u64,u64){invariant!(x<O16);let q=(x as u128*12379400392853802749>>90)as u64;(q,x-q*O8)}#[inline]fn drq8(x:u64)->(u64,u64){invariant!(x>>32==0);let q=(x as u128*184467440738>>64)as u64;(q,x-q*O8)}#[inline]fn drq4(x:u64)->(u64,u64){invariant!(x<O8);let q=(x as u128*1844674407370956>>64)as u64;(q,x-q*O4)}#[inline]pub unsafe fn du128(v:&mut P,x:u128){if x<1u128<<64{du64(v,x as u64)}else if x<H19<<64{let(y0,y1)=drh19(x);du64(v,y0);d19(v,y1);}else{let mut y0=(((x>>64)*3402823)>>64)as u64;let mut y1=x-y0 as u128*H32;if let Some(yt)=y1.checked_sub(H32){y1=yt;y0+=1;}invariant!(702<y0&&y0<3402824);d8l(v,y0);let(z0,z1)=drh_16(y1);d16(v,z0);d16(v,z1)}}#[inline]unsafe fn dmn(v:&mut*mut u8){**v=b'-';*v=(*v).add(1)}macro_rules!imi{($i:ident,$u:ident,$t:ty)=>{#[inline]pub unsafe fn$i(v:&mut P,x:$t){if x<0{dmn(v);}let a=x.unsigned_abs();invariant!(a<=<$t>::MIN.unsigned_abs());$u(v,a);}};}imi!(di8,du8,i8);imi!(di16,du16,i16);imi!(di32,du32,i32);imi!(di64,du64,i64);imi!(disize,dusize,isize);imi!(di128,du128,i128);macro_rules!imf{($f:ident,$spf:ident,$fsp:ident,$fln:ident,$fv:ident,$ty:ty,$d:ident)=>{#[inline]pub fn$f<U:Into<$ty>>(&mut self,x:U)->R{unsafe{$d(&mut self.p,x.into());}if self.p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$spf<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{*p=b' ';p=p.add(1);$d(&mut p,x.into());}self.p=p;if p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$fsp<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{$d(&mut p,x.into());*p=b' ';p=p.add(1);}self.p=p;if p>=self.limit{self.flush()?}Ok(())}#[inline]pub fn$fln<U:Into<$ty>>(&mut self,x:U)->R{let mut p=self.p;unsafe{$d(&mut p,x.into());*p=b'\n';p=p.add(1);}self.p=p;if p>=self.limit{self.flush()?}Ok(())}pub fn$fv<U:Copy+Into<$ty>>(&mut self,x:&[U])->R{if!x.is_empty(){self.$f(x[0])?;for&y in x[1..].iter(){self.$spf(y)?;}}unsafe{*self.p=b'\n';self.p=self.p.add(1);}if self.p>=self.limit{self.flush()?}Ok(())}};}const SBUF:usize=65536;const SLIM:usize=SBUF-48;pub struct FBufWriter<W:Write>{inner:Option<W>,buf:Box<[mem::MaybeUninit<u8>;SBUF]>,limit:*mut u8,p:*mut u8,}impl<W:Write>Write for FBufWriter<W>{fn write(&mut self,b:&[u8])->io::Result<usize>{let bl=b.len();let space=unsafe{self.limit.offset_from(self.p)as usize};if bl<=SBUF-SLIM{unsafe{c(b.as_ptr(),self.p,bl);self.p=self.p.add(bl);}if self.p>self.limit{self.flush()?}}else if SLIM<bl{self.flush()?;self.inner.as_mut().unwrap().write_all(b)?}else if space<bl{unsafe{c(b.as_ptr(),self.p,space);self.p=self.limit;}self.flush()?;let b=&b[space..];unsafe{c(b.as_ptr(),self.p,b.len());self.p=self.p.add(b.len())}}else{unsafe{c(b.as_ptr(),self.p,bl);self.p=self.p.add(bl)}}Ok(bl)}fn flush(&mut self)->io::Result<()>{let base=self.buf.as_mut_ptr()as*mut u8;if self.p>base{unsafe{let len=self.p.offset_from(base)as usize;self.inner.as_mut().unwrap().write_all(slice::from_raw_parts(base,len))?;self.p=base;}}Ok(())}}impl<W:Write>Drop for FBufWriter<W>{fn drop(&mut self){let _=self.flush();}}impl<W:Write>FBufWriter<W>{pub fn new(inner:W)->Self{let mut buf=Box::new([mem::MaybeUninit::uninit();SBUF]);unsafe{let base=buf.as_mut_ptr()as*mut u8;FBufWriter{inner:Some(inner),buf,limit:base.add(SLIM),p:base,}}}pub fn into_inner(mut self)->W{self.flush().unwrap();self.inner.take().unwrap()}imf!(u8,sp_u8,u8_sp,u8_ln,u8v,u8,du8);imf!(u16,sp_u16,u16_sp,u16_ln,u16v,u16,du16);imf!(u32,sp_u32,u32_sp,u32_ln,u32v,u32,du32);imf!(u64,sp_u64,u64_sp,u64_ln,u64v,u64,du64);imf!(usize,sp_usize,usize_sp,usize_ln,usizev,usize,dusize);imf!(u128,sp_u128,u128_sp,u128_ln,u128v,u128,du128);imf!(u,sp_u,u_sp,u_ln,uv,u128,du128);imf!(i8,sp_i8,i8_sp,i8_ln,i8v,i8,di8);imf!(i16,sp_i16,i16_sp,i16_ln,i16v,i16,di16);imf!(i32,sp_i32,i32_sp,i32_ln,i32v,i32,di32);imf!(i64,sp_i64,i64_sp,i64_ln,i64v,i64,di64);imf!(isize,sp_isize,isize_sp,isize_ln,isizev,isize,disize);imf!(i128,sp_i128,i128_sp,i128_ln,i128v,i128,di128);imf!(i,sp_i,i_sp,i_ln,iv,i128,di128);#[inline]pub fn byte(&mut self,b:u8)->R{unsafe{*self.p=b;self.p=self.p.add(1);}if self.p>self.limit{self.flush()?;}Ok(())}#[inline]fn sbytes(&mut self,b:&[u8])->R{invariant!(b.len()<=SBUF-SLIM);unsafe{c(b.as_ptr(),self.p,b.len());self.p=self.p.add(b.len());}if self.p>self.limit{self.flush()?;}Ok(())}#[inline]pub fn bytes(&mut self,b:&[u8])->R{self.write(b).map(|_|())}pub fn bytes_ln(&mut self,b:&[u8])->R{self.bytes(b)?;self.ln()}#[inline]pub fn str(&mut self,s:&str)->R{self.bytes(s.as_bytes())}#[inline]pub fn sp(&mut self)->R{self.byte(b' ')}#[inline]pub fn ln(&mut self)->R{self.byte(b'\n')}#[inline]pub fn yes(&mut self,x:bool)->R{if x{self.sbytes(b"Yes")}else{self.sbytes(b"No")}}#[inline]pub fn yes_ln(&mut self,x:bool)->R{if x{self.sbytes(b"Yes\n")}else{self.sbytes(b"No\n")}}}}
        pub mod input_lite3 {use crate::__cargo_equip::preludes::input_lite3::*;pub use crate::__cargo_equip::macros::input_lite3::*;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_input_lite3_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|Some(s[0]))}};($b:expr,Bytes)=>{{token($b,|s|Some(s.to_vec()))}};($b:expr,Chars)=>{{token($b,|s|Some(std::str::from_utf8(s).ok()?.chars().collect::<Vec<_>>()))}};($b:expr,u8_1)=>{read_value!($b,u8).checked_sub(1).unwrap()};($b:expr,u16_1)=>{read_value!($b,u16).checked_sub(1).unwrap()};($b:expr,u32_1)=>{read_value!($b,u32).checked_sub(1).unwrap()};($b:expr,u64_1)=>{read_value!($b,u64).checked_sub(1).unwrap()};($b:expr,usize1)=>{read_value!($b,Usize1)};($b:expr,Usize1)=>{read_value!($b,usize).checked_sub(1).unwrap()};($b:expr,Isize1)=>{read_value!($b,isize).checked_sub(1).unwrap()};($b:expr,u8)=>{u8::try_from(read_value!($b,u64)).unwrap()};($b:expr,u16)=>{u16::try_from(read_value!($b,u64)).unwrap()};($b:expr,u32)=>{u32::try_from(read_value!($b,u64)).unwrap()};($b:expr,u64)=>{{token_u64($b)}};($b:expr,u128)=>{{token_u128($b)}};($b:expr,usize)=>{usize::try_from(read_value!($b,u64)).unwrap()};($b:expr,i8)=>{i8::try_from(read_value!($b,i64)).unwrap()};($b:expr,i16)=>{i16::try_from(read_value!($b,i64)).unwrap()};($b:expr,i32)=>{i32::try_from(read_value!($b,i64)).unwrap()};($b:expr,i64)=>{{token_i64($b)}};($b:expr,i128)=>{{token_i128($b)}};($b:expr,isize)=>{isize::try_from(read_value!($b,i64)).unwrap()};($b:expr,$t:ty)=>{{token($b,|s|std::str::from_utf8(s).ok()?.parse::<$t>().ok())}};}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_lite3_read_value!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_input_lite3_input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,mut$var:ident:$t:tt$($r:tt)*)=>{let mut$var=read_value!($b,$t);input_inner!{$b$($r)*}};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}macro_rules!input_inner{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_lite3_input_inner!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_input_lite3_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);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_lite3_input!{$($tt)*})}macro_rules!invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}pub fn tokenc<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->Option<T>,g:impl Fn(&[u8])->Option<(T,usize)>,)->T{let(b,l)=loop{let b=r.fill_buf().unwrap();assert!(!b.is_empty());if let Some(p)=b.iter().position(|&c|b' '<c){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some((x,p))=g(b){r.consume(l+p);return x;}if let Some(p)=b.iter().position(|&c|c<=b' '){let t=&b[..p];invariant!(!t.is_empty());let x=f(t).unwrap();r.consume(l+p+1);return x;}let mut t=b.to_vec();r.consume(l+t.len());while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&c|c<=b' '){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}invariant!(!t.is_empty());f(&t).unwrap()}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->Option<T>)->T{tokenc(r,f,|_|None)}const E:[u64;17]={let(mut e,mut p)=([1;17],0);while p<16{e[p+1]=e[p]*10;p+=1;}e};const E8:u64=100000000;const EH:u64=E8*E8;const EW:u128=EH as _;const MH:u128=0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0;const DH:u128=MH&(MH>>2);const M8:u64=MH as _;const D8:u64=DH as _;#[inline]fn q2(b:u16)->u64{b.wrapping_mul(2561)as u64>>8}#[inline]fn q4(b:u32)->u64{((b.wrapping_mul(2561)>>8)&0xff00ff).wrapping_mul(6553601)as u64>>16}#[inline]fn q8(b:u64)->u64{((((b.wrapping_mul(2561)>>8)&0xff00ff00ff00ff).wrapping_mul(6553601)>>16)&0xffff0000ffff).wrapping_mul((10000<<32)+1)>>32}#[inline]fn q16(b:u128)->u64{q8(b as u64)*E8+q8((b>>64)as u64)}#[inline]fn p2(b:[u8;2])->u64{q2(u16::from_le_bytes(b)&3855)}#[inline]fn p4(b:[u8;4])->u64{q4(u32::from_le_bytes(b)&0xf0f0f0f)}#[inline]fn p8(b:[u8;8])->u64{q8(u64::from_le_bytes(b)&(M8>>4))}#[inline]fn p16(b:[u8;16])->u64{q16(u128::from_le_bytes(b)&(MH>>4))}#[inline]fn p(s:&[u8])->u64{match s.len(){0=>0,1=>(s[0]&15)as u64,2=>p2(s.try_into().unwrap()),3=>((s[0]&15)as u64)*100+p2(s[1..].try_into().unwrap()),4=>p4(s.try_into().unwrap()),5..=8=>p8(u64::to_le_bytes((u32::from_le_bytes(s[..4].try_into().unwrap())<<(8*(8-s.len())))as u64|((u32::from_le_bytes(s[(s.len()-4)..].try_into().unwrap())as u64)<<32),)),9..=16=>{p8(u64::to_le_bytes(u64::from_le_bytes(s[..8].try_into().unwrap())<<(8*(16-s.len())),))*E8+p8(s[(s.len()-8)..].try_into().unwrap())}_=>unreachable!(),}}pub fn parse_u64(s:&[u8])->Option<u64>{match s.len(){0..=16=>Some(p(s)),17..=20=>(p4(u32::to_le_bytes(u32::from_le_bytes(s[..4].try_into().unwrap())<<(8*(20-s.len())),))as u64).checked_mul(EH)?.checked_add(p16(s[(s.len()-16)..].try_into().unwrap())),_=>{let c=s.rchunks_exact(16);let l=p(c.remainder());c.rfold(Some(l),|a,b|{a?.checked_add(EH)?.checked_add(p16(b.try_into().unwrap()))})}}}pub fn parse_u128(s:&[u8])->Option<u128>{match s.len(){0..=19=>Some(parse_u64(s)?as u128),20..=35=>{let(t,u)=s.split_at(s.len()-16);(parse_u64(t)?as u128).checked_mul(EW)?.checked_add(p16(u.try_into().unwrap())as u128)}36..=39=>(p8(u64::to_le_bytes(u64::from_le_bytes(s[..8].try_into().unwrap())<<(8*(40-s.len())),))as u128).checked_mul(EW*EW)?.checked_add(p16(s[s.len()-32..][..16].try_into().unwrap())as u128*EW+p16(s[s.len()-16..].try_into().unwrap())as u128,),_=>{let c=s.rchunks_exact(16);let l=p(c.remainder())as u128;c.rfold(Some(l),|a,b|{a?.checked_mul(EW)?.checked_add(p16(b.try_into().unwrap())as u128)})}}}pub fn parse_i64(s:&[u8])->Option<i64>{if s.starts_with(b"-"){parse_u64(&s[1..]).and_then(|v|0i64.checked_sub_unsigned(v))}else{parse_u64(s).and_then(|v|i64::try_from(v).ok())}}pub fn parse_i128(s:&[u8])->Option<i128>{if s.starts_with(b"-"){parse_u128(&s[1..]).and_then(|v|0i128.checked_sub_unsigned(v))}else{parse_u128(s).and_then(|v|i128::try_from(v).ok())}}pub fn cparse_u64(mut s:&[u8])->Option<(u64,usize)>{if s.len()<24{return None;}let mut v={let b=u64::from_le_bytes(s[..8].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(q8(b<<(64-8*e)),e+1)}else{(0,1)});}q8(b)};{let b=u64::from_le_bytes(s[8..16].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v*E[e]+q8(b<<(64-8*e)),e+9)}else{(v,9)});}v=v*E8+q8(b);}{let b=u64::from_le_bytes(s[16..24].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v.checked_mul(E[e])?.checked_add(q8(b<<(64-8*e)))?,e+17,)}else{(v,17)});}v=v.checked_mul(E8)?.checked_add(q8(b))?;}s=&s[24..];let mut c=25;while s.len()>7{let b=u64::from_le_bytes(s[..8].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;if e>0{v=v.checked_mul(E[e])?.checked_add(q8(b<<(64-8*e)))?;c+=e;}return Some((v,c));}v=v.checked_mul(E8)?.checked_add(q8(b))?;s=&s[8..];c+=8;}None}pub fn cparse_u128(mut s:&[u8])->Option<(u128,usize)>{if s.len()<40{return None;}let mut v={let b=u64::from_le_bytes(s[..8].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(q8(b<<(64-8*e))as u128,e+1)}else{(0,1)});}q8(b)};{let b=u64::from_le_bytes(s[8..16].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{((v*E[e]+q8(b<<(64-8*e)))as u128,e+9)}else{(v as u128,9)});}v=v*E8+q8(b);}let v2={let b=u64::from_le_bytes(s[16..24].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v as u128*E[e]as u128+q8(b<<(64-8*e))as u128,e+17,)}else{(v as u128,17)});}q8(b)};let v3={let b=u64::from_le_bytes(s[24..32].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v as u128*E[e+8]as u128+(v2*E[e]+q8(b<<(64-8*e)))as u128,e+25,)}else{(v as u128*E8 as u128+v2 as u128,25)});}q8(b)};let mut v=v as u128*EW+(v2*E8+v3)as u128;{let b=u64::from_le_bytes(s[32..40].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v.checked_mul(E[e]as u128)?.checked_add(q8(b<<(64-8*e))as u128)?,e+33,)}else{(v,33)});}v=v.checked_mul(E8 as u128)?.checked_add(q8(b)as u128)?;}s=&s[40..];let mut c=41;while s.len()>7{let b=u64::from_le_bytes(s[..8].try_into().unwrap())^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;if e>0{v=v.checked_mul(E[e]as u128)?.checked_add(q8(b<<(64-8*e))as u128)?;c+=e;}return Some((v,c));}v=v.checked_mul(E8 as u128)?.checked_add(q8(b)as u128)?;s=&s[8..];c+=8;}None}pub fn cparse_i64(s:&[u8])->Option<(i64,usize)>{if s.starts_with(b"-"){cparse_u64(&s[1..]).and_then(|(v,c)|Some((0i64.checked_sub_unsigned(v)?,c+1)))}else{cparse_u64(s).and_then(|(v,c)|Some((i64::try_from(v).ok()?,c)))}}pub fn cparse_i128(s:&[u8])->Option<(i128,usize)>{if s.starts_with(b"-"){cparse_u128(&s[1..]).and_then(|(v,c)|Some((0i128.checked_sub_unsigned(v)?,c+1)))}else{cparse_u128(s).and_then(|(v,c)|Some((i128::try_from(v).ok()?,c)))}}pub fn token_u64<R:std::io::BufRead>(r:&mut R)->u64{tokenc(r,parse_u64,cparse_u64)}pub fn token_u128<R:std::io::BufRead>(r:&mut R)->u128{tokenc(r,parse_u128,cparse_u128)}pub fn token_i64<R:std::io::BufRead>(r:&mut R)->i64{tokenc(r,parse_i64,cparse_i64)}pub fn token_i128<R:std::io::BufRead>(r:&mut R)->i128{tokenc(r,parse_i128,cparse_i128)}}
        pub mod change {pub trait Change{fn chmax(&mut self,x:Self)->bool;fn chmin(&mut self,x:Self)->bool;}impl<T:PartialOrd>Change for T{fn chmax(&mut self,x:T)->bool{if*self<x{*self=x;true}else{false}}fn chmin(&mut self,x:T)->bool{if*self>x{*self=x;true}else{false}}}}
        pub mod invariant {pub use crate::__cargo_equip::macros::invariant::*;#[macro_export]macro_rules!__cargo_equip_macro_def_invariant_invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}macro_rules!invariant{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_invariant_invariant!{$($tt)*})}}
        pub mod __mizar_competitive_misc_primint_0_0_0 {use std::ops;pub trait UPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+ops::AddAssign+ops::SubAssign+ops::MulAssign+ops::DivAssign+ops::RemAssign+ops::Shl<u32,Output=Self>+ops::Shr<u32,Output=Self>+ops::ShlAssign<u32>+ops::ShrAssign<u32>+ops::BitAnd<Output=Self>+ops::BitOr<Output=Self>+ops::BitXor<Output=Self>+ops::BitAndAssign+ops::BitOrAssign+ops::BitXorAssign+ops::Not<Output=Self>+std::convert::From<u8>{const BITS:u32;fn count_zeros(self)->u32;fn count_ones(self)->u32;fn trailing_zeros(self)->u32;fn leading_zeros(self)->u32;fn checked_add(self,rhs:Self)->Option<Self>;fn checked_sub(self,rhs:Self)->Option<Self>;fn checked_mul(self,rhs:Self)->Option<Self>;fn checked_pow(self,exp:u32)->Option<Self>;fn wrapping_add(self,rhs:Self)->Self;fn wrapping_sub(self,rhs:Self)->Self;fn wrapping_neg(self)->Self;fn wrapping_mul(self,rhs:Self)->Self;fn overflowing_add(self,rhs:Self)->(Self,bool);fn overflowing_sub(self,rhs:Self)->(Self,bool);fn overflowing_neg(self)->(Self,bool);fn overflowing_mul(self,rhs:Self)->(Self,bool);fn pow(self,exp:u32)->Self;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;fn as_u8(self)->u8;fn as_u16(self)->u16;fn as_u32(self)->u32;fn as_u64(self)->u64;fn as_u128(self)->u128;fn as_usize(self)->usize;fn from_u32(x:u32)->Self;fn from_u64(x:u64)->Self;fn from_u128(x:u128)->Self;fn from_usize(x:usize)->Self;}macro_rules!impl_uprimint{($t:ty)=>{impl UPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn count_zeros(self)->u32{self.count_zeros()}fn count_ones(self)->u32{self.count_ones()}fn trailing_zeros(self)->u32{self.trailing_zeros()}fn leading_zeros(self)->u32{self.leading_zeros()}fn checked_add(self,rhs:$t)->Option<$t>{self.checked_add(rhs)}fn checked_sub(self,rhs:$t)->Option<$t>{self.checked_sub(rhs)}fn checked_mul(self,rhs:$t)->Option<$t>{self.checked_mul(rhs)}fn checked_pow(self,exp:u32)->Option<$t>{self.checked_pow(exp)}fn wrapping_add(self,rhs:$t)->$t{self.wrapping_add(rhs)}fn wrapping_sub(self,rhs:$t)->$t{self.wrapping_sub(rhs)}fn wrapping_neg(self)->$t{self.wrapping_neg()}fn wrapping_mul(self,rhs:$t)->$t{self.wrapping_mul(rhs)}fn overflowing_add(self,rhs:$t)->($t,bool){self.overflowing_add(rhs)}fn overflowing_sub(self,rhs:$t)->($t,bool){self.overflowing_sub(rhs)}fn overflowing_neg(self)->($t,bool){self.overflowing_neg()}fn overflowing_mul(self,rhs:$t)->($t,bool){self.overflowing_mul(rhs)}fn pow(self,exp:u32)->Self{self.pow(exp)}fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}fn as_u8(self)->u8{self as u8}fn as_u16(self)->u16{self as u16}fn as_u32(self)->u32{self as u32}fn as_u64(self)->u64{self as u64}fn as_u128(self)->u128{self as u128}fn as_usize(self)->usize{self as usize}fn from_u32(x:u32)->Self{x as Self}fn from_u64(x:u64)->Self{x as Self}fn from_u128(x:u128)->Self{x as Self}fn from_usize(x:usize)->Self{x as Self}}};}impl_uprimint!(u8);impl_uprimint!(u16);impl_uprimint!(u32);impl_uprimint!(u64);impl_uprimint!(u128);impl_uprimint!(usize);pub trait IPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Neg<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+std::convert::From<i8>{const BITS:u32;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;}macro_rules!impl_iprimint{($t:ty)=>{impl IPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}}};}impl_iprimint!(i8);impl_iprimint!(i16);impl_iprimint!(i32);impl_iprimint!(i64);impl_iprimint!(i128);impl_iprimint!(isize);}
    }

    pub(crate) mod macros {
        pub mod minmod {}
        pub mod fastout {}
        pub mod input_lite3 {pub use crate::{__cargo_equip_macro_def_input_lite3_input as input,__cargo_equip_macro_def_input_lite3_input_inner as input_inner,__cargo_equip_macro_def_input_lite3_read_value as read_value};}
        pub mod change {}
        pub mod invariant {pub use crate::__cargo_equip_macro_def_invariant_invariant as invariant;}
        pub mod __mizar_competitive_misc_primint_0_0_0 {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::input_lite3::*};}

    mod preludes {
        pub mod minmod {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{change,invariant,__mizar_competitive_misc_primint_0_0_0 as primint};}
        pub mod fastout {}
        pub mod input_lite3 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::input_lite3::*;}
        pub mod change {}
        pub mod invariant {}
        pub mod __mizar_competitive_misc_primint_0_0_0 {}
    }
}