If \(y\) has \(d\) digits,

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

so the condition is equivalent to

\[ \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} \]

Therefore, whether the condition is satisfied is solely determined by \(x\) and \(d\), the number of digits in \(y\).
The number of digits of \(y\) satisfies \(1 \leq d \leq 19\). Consider solving the problem for each \(d\). In other words, let us fix \(d\). A desired \(x\) satisfies

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

Putting \(g = \gcd(10^d - 1, M)\), it is equivalent to

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

Thus, the number of \(x\) not greater than \(M\) satisfying the condition is

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

.

We can also find the number of \(y\) with \(d\) digits, so the number of pairs \((x,y)\) satisfying the conditions can be computed as the sum of these two values.

The problem can be solved by appropriately implementing the idea above. The complexity is \(\mathrm{O}(\log N \log M)\), where finding the greatest common divisor \(g\) is the bottleneck. Note that some implementation may require storing \(10^{19}\) to a variable, leading to an overflow of a \(64\)-bit signed integer type.

• Sample code (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";
  }
}