AT_abc460_e [ABC460E] x + y ≡ x + y

For positive integers $ a $ and $ b $ , define $ \mathrm{concat}(a, b) $ as the integer formed by writing $ a $ and $ b $ one after another. More formally, $ \mathrm{concat}(a, b) $ is defined as follows. - Let $ A $ and $ B $ be the strings formed by writing $ a $ and $ b $ in decimal, respectively. Let $ C $ be the string formed by concatenating $ A $ and $ B $ in this order. The value of $ C $ interpreted as an integer in decimal notation is $ \mathrm{concat}(a, b) $ . For example, if $ a = 123 $ and $ b = 45 $ , then $ \mathrm{concat}(a, b) = 12345 $ . You are given positive integers $ N $ and $ M $ . Find the number, modulo $ 998244353 $ , of pairs $ (x, y) $ of positive integers not greater than $ N $ such that $ \mathrm{concat}(x, y) \equiv x + y \pmod{M} $ . You are given $ T $ test cases; solve each one.

The input is given from Standard Input in the following format, where $ \mathrm{case}_i $ denotes the $ i $ -th test case: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ M $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case. For each test case, output the number, modulo $ 998244353 $ , of pairs $ (x, y) $ satisfying the condition.

### Sample Explanation 1 For the first test case, three pairs $ (x, y) $ satisfy the condition: $ (2, 1), (2, 2), (2, 3) $ . ### Constraints - $ 1 \leq T \leq 10^4 $ - $ 1 \leq N \leq 10^{18} $ - $ 2 \leq M \leq 10^9 $ - All input values are integers.