fn main() {
    let mut tb = String::new();
    std::io::stdin().read_line(&mut tb).ok();
    let tb: Vec<isize> = tb.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let t = tb[0] as usize;
    let b = tb[1];
    let vals = (0..t).map(|_| {
            let mut temp = String::new();
            std::io::stdin().read_line(&mut temp).ok();
            let temp: isize = temp.trim().parse().unwrap();
            temp
        })
        .collect::<Vec<_>>();

    for &v in vals.iter() {
        if v == 0 {
            println!("0");
            continue;
        }
        let mut result = vec![];
        let mut val = v;
        while val != 0 {
            let mut modval = val % b;
            val = val / b;
            if modval < 0 {
                val += 1;
                modval += b.abs();
            }
            result.push(modval);
        }
        println!("{}", result.iter().rev().map(|v| v.to_string()).collect::<Vec<_>>().join(""));
    }
}