// Author: @Drydock
use std::io::{self, Read};

fn main() {
    solve();
}

fn solve() {
    let mut s = String::new();
    io::stdin().read_to_string(&mut s).unwrap();
    let mut it = I::new(&s);
    let t: usize = it.n();
    let mut o = String::new();
    for _ in 0..t {
        let mut x: u64 = it.n();
        let mut k: u64 = it.n();
        let mut v: Vec<(u64, u64)> = Vec::new();
        let mut n = x;
        let mut c = 0;
        while n % 2 == 0 {
            c += 1;
            n /= 2;
        }
        if c > 0 { v.push((2, c)); c = 0; }
        let mut i = 3;
        while i * i <= n {
            if n % i == 0 {
                c = 0;
                while n % i == 0 {
                    c += 1;
                    n /= i;
                }
                v.push((i, c));
            }
            i += 2;
        }
        if n > 1 { v.push((n, 1)); }
        if v.is_empty() { v.push((x, 1)); }
        v.sort_by_key(|p| p.0);
        let mut e0 = v[0].1;
        let mut sum: u64 = 0;
        for &(_, e) in &v { sum += e; }
        let pairs = sum - e0;
        if k >= 2 && v.len() > 1 {
            let mut p2 = k / 2;
            if p2 >= pairs {
                e0 += pairs;
                v.truncate(1);
                k -= pairs * 2;
            } else {
                let mut r = p2;
                let mut idx = v.len();
                while r > 0 {
                    idx -= 1;
                    let take = if v[idx].1 <= r { v[idx].1 } else { r };
                    r -= take;
                    e0 += take;
                    v[idx].1 -= take;
                    if v[idx].1 == 0 { v.remove(idx); }
                    if idx == 0 { break; }
                }
                k -= p2 * 2;
            }
        }
        if k > 0 && k % 2 == 1 {
            e0 += 1;
        }
        v[0].1 = e0;
        let mut ans: u128 = 1;
        for &(p, e) in &v {
            let pp = p as u128;
            for _ in 0..e { ans *= pp; }
        }

        o.push_str(&format!("{}\n", ans));
    }
    print!("{}", o);
}

struct I<'a> { w: std::str::SplitWhitespace<'a> }

impl<'a> I<'a> {
    fn new(s: &'a str) -> Self { Self { w: s.split_whitespace() } }
    fn n<T: std::str::FromStr>(&mut self) -> T { self.w.next().unwrap().parse().ok().unwrap() }
}