AtCoder Beginner Contest 460 E

https://atcoder.jp/contests/abc460/tasks/abc460_e

の桁数をとすると、

なので、

だから、はの倍数です。
i128を使うと簡単ですね。

// x + y ≡ x + y
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn gcd(a: i128, b: i128) -> i128 {
    if b == 0 {
        a
    }
    else {
        gcd(b, a % b)
    }
}

fn num_digits(mut n: i128) -> u32 {
    let mut num: u32 = 1;
    while n >= 10 {
        n /= 10;
        num += 1
    }
    num
}


//////////////////// process ////////////////////

fn read_test() -> (i128, i128) {
    let v: Vec<i128> = read_vec();
    let (N, M) = (v[0], v[1]);
    (N, M)
}

const D: i128 = 998244353;

fn F_each(N: i128, M: i128) -> i128 {
    let E = num_digits(N);  // Nは何桁か
    let mut counter: i128 = 0;
    for e in 1..E+1 {
        let L = 10i128.pow(e-1);
        let U1 = 10i128.pow(e) - 1;
        let U = N.min(U1);
        let d = M / gcd(U1, M);
        counter += N / d * (U - L + 1)
    }
    counter.rem_euclid(D)
}

fn F(T: usize) {
    for _ in 0..T {
        let (N, M) = read_test();
        println!("{}", F_each(N, M))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}