解题思路

先明确题意： 题目中的“最大可能值”与“最小可能值”，指的是满足条件的十进制数本身最大/最小，最后只需要输出这两个数分别对 $k$ 取模后的结果。

也就是说，问题并不是“在所有合法数字中，模 $k$ 的结果最大/最小是多少”，而是：

1. 先确定长度为 $m$ 的合法十进制数中，谁最大；
2. 再确定谁最小；

题目内容

给定一个整数 $m$ 。考虑长度为 $m$ 的十进制数字串 $d_1 d_2 \dots d_m$ ，其对应的十进制数需满足：

• $d_1 \neq 0$ （不含前导零；特别地，若 $m = 1$ ，允许取 $d_1 = 0$ ）；
• 相邻数字不同，即对所有 $1 \le i < m$ 均有 $d_i \neq d_{i+1}$ 。

请输出该长度为 $m$ 的十进制数字串 $d_1 d_2 \dots d_m$ 的最大可能值与最小可能值。由于这两个值可能很大，给定正整数 $k$ ，只需输出这两个值分别对 $k$ 取模后的结果。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t$ （ $1 \le t \le 10^4$ ）表示数据组数，每组测试数据描述如下：

• 在一行上输入两个整数 $m, k$ （ $1 \le m \le 2 \times 10^5$ ； $1 \le k \le 10^9$ ）。

除此之外，保证单个测试文件的 $m$ 之和不超过 $2 \times 10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出两个整数，分别表示最大可能值与最小可能值对 $k$ 取模后的结果。

样例1

输入

2
1 100
2 7

输出

9 0
0 3

说明

在这组测试数据中：

• 当 $m = 1$ 、 $k = 100$ 时，最大值为 $9$ ，最小值为 $0$ ，输出 $9 0$ ；
• 当 $m = 2$ 、 $k = 7$ 时，最大值为 $98$ ， $98 \bmod 7 = 0$ ；最小值为 $10$ ， $10 \bmod 7 = 3$ ，输出 $0 3$ 。