\(y\) の桁数を \(d\) とすると

\[\mathrm{concat}(x,y) = x \cdot 10^d + y\]

であり、条件は

\[ \begin{aligned} \mathrm{concat}(x,y) &\equiv x+y \pmod{M}\\ \iff x \cdot10^d + y &\equiv x+y \pmod{M} \\ \iff (10^d - 1) x &\equiv 0 \pmod{M} \end{aligned} \]

と同値変形できます。このことから \(x\) 、および \(y\) の桁数 \(d\) のみによって条件を満たすかどうかが決まることがわかります。
\(y\) の桁数 \(d\) は \(1 \leq d \leq 19\) を満たします。それぞれの \(d\) に対して問題を解くことを考えます。つまり、\(d\) を固定して考えましょう。求めたい \(x\) は

\[(10^d - 1) x \equiv 0 \pmod{M}\]

を満たす \(x\) です。ここで \(g = \gcd(10^d - 1, M)\) と置くと条件は

\[x \equiv 0 \pmod{M / g}\]

と等価です。よって条件を満たす \(N\) 以下の正整数 \(x\) の個数は

\[\left\lfloor \frac{N}{M/g} \right\rfloor\]

個になります。桁数が \(d\) である \(y\) の個数も求まるので、この時に条件を満たす \((x,y)\) の個数はこの \(2\) つの値の積として求まります。

以上の内容を踏まえて適切に実装することでこの問題を解くことが出来ます。時間計算量は最大公約数 \(g\) を求める部分がボトルネックとなり \(\mathrm{O}(\log N \log M)\) です。 計算方法によっては変数に格納する値に \(10^{19}\) が登場して符号付き \(64\) bit 整数がオーバーフローしうる点に注意してください。

• 実装例 (C++)

#include <iostream>
#include <numeric>
using namespace std;

using u64 = unsigned long long;
const u64 mod = 998244353;
const int dmax = 19;
u64 p10[dmax + 1];
int main() {
  p10[0] = 1;
  for (int i = 1; i <= dmax; i++) p10[i] = p10[i - 1] * 10;

  int T;
  cin >> T;
  while (T--) {
    u64 N, M;
    cin >> N >> M;
    u64 ans = 0;
    for (int d = 1; d <= dmax; d++) {
      u64 L = p10[d - 1];
      u64 R = min(p10[d], N + 1);
      if (L >= R) break;
      u64 g = gcd(p10[d] - 1, M);
      ans += ((R - L) % mod) * ((N / (M / g)) % mod);
      ans %= mod;
    }
    cout << ans << "\n";
  }
}