fn main() {
    let mut t = String::new();
    std::io::stdin().read_line(&mut t).ok();
    let t: usize = t.trim().parse().unwrap();
    for _ in 0..t {
        let mut nm = String::new();
        std::io::stdin().read_line(&mut nm).ok();
        let nm: Vec<&str> = nm.trim().split_whitespace().collect();
        let n = nm[0].chars().map(|c| c as usize - '0' as usize).collect::<Vec<_>>();
        let m = nm[1].parse::<usize>().unwrap();
        let mut summary = n[0];
        for i in 1..n.len() {
            summary *= 10;
            summary += n[i];
            summary %= m;
        }
        println!("{}", summary * (summary + 1) / 2 % m);
    }
}