#![allow(unexpected_cfgs, unused_imports, unused_macros)]
use std::{
    cmp::*,
    collections::*,
    io::{BufRead, Write, stderr, stdin, stdout},
    iter::*,
    mem::*,
    ops::*,
    str::*,
};

static mut DBG_INDENT: usize = 0;
#[rustfmt::skip]
macro_rules! DB { () => { let _debug_block = DBBlock::new(); }; }
macro_rules! eprintln { ($($arg:tt)*) => { if cfg!(LOCAL) { unsafe{std::eprint!("{}", "  ".repeat(DBG_INDENT));} std::eprintln!($($arg)*); } }; }
macro_rules! dbg { ($($arg:expr),*) => { eprintln!(concat!($("[", stringify!($arg), " = {:?}] "),*) $(, $arg)*) }}
macro_rules! wrln { ($writer: expr, $($arg:expr),*) => {std::writeln!($writer, $($arg,)*).unwrap()}}
macro_rules! wr { ($writer: expr, $($arg:expr),*) => {std::write!($writer, $($arg,)*).unwrap()}}

struct CongurentSolver {
    /// cache a single value as it is mostly used for `u = 2 * (n - 1)` and `v = 2 * (m - 1)`.
    /// this helps remove a log factor from the final solution
    cached_exgcd: Option<((usize, usize, usize), (usize, usize, usize))>,
}

impl CongurentSolver {
    pub fn new() -> Self {
        Self { cached_exgcd: None }
    }

    fn set_cached_exgcd(&mut self, u: usize, v: usize, m: usize) {
        let new_res = self.exgcd(u, v, m);
        self.cached_exgcd = Some(((u, v, m), new_res));
    }

    // return (g, x, y), where:
    // - g = gcd(u, v)
    // - x, y must satisfies: (u * x + v * y) % m == g % m
    fn exgcd(&self, u: usize, v: usize, m: usize) -> (usize, usize, usize) {
        match &self.cached_exgcd {
            Some((cached_arg, cached_result)) if *cached_arg == (u, v, m) => {
                // eprintln!("cache hit");
                return *cached_result;
            }
            _ => {}
        }
        // u * x + v * y == g
        // v * x1 + (u % v) * y1 == g
        // (v * (u / v) + u % v) * x + v * y == g
        // x == y1
        // u * q * x + v * y == v * x1
        // y = (v * x1 - v * q * x) / v

        if v == 0 {
            return (u, 1, 0);
        }
        let (g, x1, y1) = self.exgcd(v, u % v, m);
        let q = u / v;
        let x = y1;
        let y = (m + x1 - q * x % m) % m;
        return (g, x, y);
    }

    // Find x such that a * x == b (mod m)
    // Return x and m / gcd(a, m)
    // Note: passing b == 1 to find modulo inversion
    fn solve_congruent(&self, a: usize, b: usize, m: usize) -> Option<(usize, usize)> {
        match a {
            0 => (b == 0).then_some((0, 1)),
            1 => Some((b, m)),
            _ => {
                let (g, x, _) = self.exgcd(a, m, m);
                let m = m / g;
                (b % g == 0).then_some((x * (b / g) % m, m))
            }
        }
    }

    // Find k such that
    // k * a = r (mod h)
    // k * b = c (mod w)
    // This is basically CRT with extra steps
    fn solve_congruent_2(&self, a: usize, r: usize, h: usize, b: usize, c: usize, w: usize) -> Option<usize> {
        let (r, h) = self.solve_congruent(a, r, h)?;
        let (c, w) = self.solve_congruent(b, c, w)?;
        // k = r (mod h)
        // k = c (mod w)
        // k = r + h * x
        // r + h * x = c (mod w)
        // h * x = c - r (mod w)
        let (x, _) = self.solve_congruent(h, (c + w - r % w) % w, w)?;
        let k = r + h * x;
        Some(k)
    }

    /// Count the number of solutions to the congruent equation a * x == b (mod m)
    /// such that (0 <= x <= t)
    fn count_coungruent(&self, a: usize, b: usize, m: usize, t: usize) -> Option<usize> {
        let (x, m) = self.solve_congruent(a, b, m)?;
        Some(if t < x { 0 } else { (t - x) / m + 1 })
    }
}

fn add_mod(a: usize, b: usize, modulo: usize) -> usize {
    if a + b >= modulo { a + b - modulo } else { a + b }
}

fn sub_mod(a: usize, b: usize, modulo: usize) -> usize {
    if a < b { a + modulo - b } else { a - b }
}

fn iter_2_uniq(m1: usize, m2: usize) -> impl Iterator<Item = usize> {
    once(m1).chain((m1 != m2).then_some(m2))
}

struct SolverSingle {
    n: usize,
    m: usize,
    rb: usize,
    rc: usize,

    period_row: usize,
    period_col: usize,
    period: usize,

    cs: CongurentSolver,
}

impl SolverSingle {
    fn new(n: usize, m: usize, rb: usize, rc: usize) -> Self {
        let (period_row, period_col) = (2 * (n - 1), 2 * (m - 1));
        let mut cs = CongurentSolver::new();
        cs.set_cached_exgcd(period_row, period_col, period_col);

        let period = period_row / cs.exgcd(period_row, period_col, period_col).0 * period_col;

        Self { n, m, rb, rc, period_row, period_col, period, cs }
    }

    fn num_clean_1d(&self, n: usize, pos: usize, start: usize, t: usize) -> usize {
        let p = 2 * (n - 1);
        // Answer is the number of i (0 <= i <= t) such that
        // start + i == +-pos (mod p)
        // i = +- pos - start (mod p)

        let nstart = sub_mod(0, start, p);

        iter_2_uniq(add_mod(nstart, pos, p), sub_mod(nstart, pos, p))
            .map(|m| self.cs.count_coungruent(1, m, p, t).unwrap())
            .sum()
    }

    fn num_clean_row(&self, r: usize, t: usize) -> usize {
        self.num_clean_1d(self.n, r, self.rb, t)
    }

    fn num_clean_col(&self, c: usize, t: usize) -> usize {
        self.num_clean_1d(self.m, c, self.rc, t)
    }

    fn count_meet_cell(&self, r: usize, c: usize, t: usize) -> usize {
        let (pr, pc) = (self.period_row, self.period_col);
        // Answer is the number of i (0 <= i <= t) such that both the following is true
        //      rb + i == +-r (mod pr)
        //      rc + i == +-c (mod pc)
        // or
        //      i = +-r - rb (mod pr)
        //      i = +-c - rc (mod pc)

        let (nrb, nrc) = (sub_mod(0, self.rb, pr), sub_mod(0, self.rc, pc));

        iter_2_uniq(add_mod(nrb, r, pr), sub_mod(nrb, r, pr))
            .flat_map(|mr| iter_2_uniq(add_mod(nrc, c, pc), sub_mod(nrc, c, pc)).map(move |mc| (mr, mc)))
            .map(|(mr, mc)| {
                let Some(x) = self.cs.solve_congruent_2(1, mr, pr, 1, mc, pc) else {
                    return 0;
                };
                let x = x % self.period;
                self.cs.count_coungruent(1, x, self.period, t).unwrap()
            })
            .sum::<usize>()
    }

    fn num_clean_cell(&self, r: usize, c: usize, t: usize) -> usize {
        self.num_clean_row(r, t) + self.num_clean_col(c, t) - self.count_meet_cell(r, c, t)
    }

    fn cleanest(&self, t: usize) -> usize {
        let mut res = usize::MAX;
        {
            for i in 0..self.n {
                res = res
                    .min(self.num_clean_cell(i, 0, t))
                    .min(self.num_clean_cell(i, self.m - 1, t));
            }
            for i in 1..self.m - 1 {
                res = res
                    .min(self.num_clean_cell(0, i, t))
                    .min(self.num_clean_cell(self.n - 1, i, t));
            }
        }

        let lim = 10 * max(self.n, self.m);
        if t < lim {
            let (mut rb, mut rc) = (self.rb, self.rc);
            let (mut dr, mut dc) = (1, 1);

            fn inc_pos(x: usize, d: isize, n: usize) -> (usize, isize) {
                if x == 0 {
                    (1, 1)
                } else if x == n - 1 {
                    (n - 2, -1)
                } else {
                    (x.checked_add_signed(d).unwrap(), d)
                }
            }
            res = res.min(self.num_clean_cell(rb, rc, t));
            for _ in 0..t {
                (rb, dr) = inc_pos(rb, dr, self.n);
                (rc, dc) = inc_pos(rc, dc, self.m);
                res = res.min(self.num_clean_cell(rb, rc, t));
            }
        }

        res
    }
}

fn solve(n: usize, m: usize, k: usize, rb: usize, rc: usize) -> usize {
    let (rb, rc) = (rb - 1, rc - 1);
    let ss = SolverSingle::new(n, m, rb, rc);

    let (mut l, mut r) = (0, 1);
    while ss.cleanest(r) < k {
        (l, r) = (r, r * 2);
    }
    while l < r {
        let m = (l + r) / 2;
        if ss.cleanest(m) < k {
            l = m + 1;
        } else {
            r = m;
        }
    }

    l
}

fn main() {
    let mut scan = Scan::new();
    // let mut writer = stdout();  // for interactive
    let stdout = stdout().lock();
    #[allow(unused)]
    let mut writer = std::io::BufWriter::new(stdout);

    // let num_test = 1;
    let num_test: usize = scan.next();
    for test_case in 1..=num_test {
        DB!();
        dbg!(test_case);
        let n: usize = scan.next();
        let m: usize = scan.next();
        let k: usize = scan.next();
        let rb: usize = scan.next();
        let rc: usize = scan.next();

        let res = solve(n, m, k, rb, rc);

        wrln!(writer, "{}", res);
    }
}

////////////////////////////////////////////////////////////////////////////////
//{{{
struct Scan {
    stdin: std::io::StdinLock<'static>,
    buff: Vec<u8>,
    pos: usize,
}
#[allow(dead_code)]
#[allow(unused_variables)]
impl Scan {
    fn new() -> Self {
        return Self { stdin: std::io::stdin().lock(), buff: vec![], pos: 0 };
    }

    fn next_token(&mut self) -> Option<&[u8]> {
        while self.pos < self.buff.len() && self.buff[self.pos].is_ascii_whitespace() {
            self.pos += 1;
        }
        if self.pos >= self.buff.len() {
            self.buff.clear();
            self.pos = 0;
            if self.stdin.read_until(b'\n', &mut self.buff).is_err() {
                return None;
            }
            return self.next_token();
        }
        let start = self.pos;
        while self.pos < self.buff.len() && !self.buff[self.pos].is_ascii_whitespace() {
            self.pos += 1;
        }
        let token = &self.buff[start..self.pos];
        return Some(token);
    }

    fn next<T: FromStr>(&mut self) -> T {
        return self.next_opt().unwrap();
    }

    fn next_opt<T: FromStr>(&mut self) -> Option<T> {
        let token = self.next_token()?;
        let s = unsafe { std::str::from_utf8_unchecked(token) };
        return s.parse::<T>().ok();
    }

    fn read_line(&mut self) -> Option<String> {
        let mut line = String::new();
        return self.stdin.read_line(&mut line).map(|_| line).ok();
    }

    // empty line will be consumed too
    fn read_line_till_empty(&mut self) -> Option<String> {
        self.read_line().filter(|line| !line.is_empty())
    }
}

pub struct DBBlock;
#[rustfmt::skip]
impl DBBlock {
    pub fn new() -> Self {
        if cfg!(LOCAL) { eprintln!("{{"); unsafe { DBG_INDENT += 1; } }
        Self {}
    }
}
#[rustfmt::skip]
impl Drop for DBBlock {
    fn drop(&mut self) {
        if cfg!(LOCAL) { unsafe { DBG_INDENT -= 1; } eprintln!("}}"); }
    }
} //}}}