每天散步时,阿丽娜注意到地上写着一长串数字。现在 Alina 想要找到一些长度相同但不带前导零的正数,使得这两个数的和是回文数。
回想一下,如果一个数字从右到左和从左到右读起来相同,则该数字被称为回文。例如,数字 $$$121, 66, 98989$$$ 是回文,$$$103, 239, 1241$$$ 不是回文。
Alina 知道有效的号码总是存在的。帮她找一个吧!
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。接下来是 $$$t$$$ 测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — 写在地上的数字的长度。
第二行包含不带前导零的正 $$$n$$$ 位整数 — 数字本身。
保证所有测试用例的值 $$$n$$$ 之和不超过 $$$100\,000$$$。
输出
对于每个 $$$t$$$ 测试用例打印一个答案 - 一个不带前导零的正 $$$n$$$ 位整数,这样输入整数与该数字的总和是回文。
我们可以证明至少存在一个满足约束的数字。如果有多个解,可以输出任意一个。
示例
输入 #1
3 2 99 4 1023 3 385
输出 #1
32 8646 604
注意
在第一个测试用例中 $$$99 + 32 = 131$$$ 是回文。请注意,另一个答案是 $$$12$$$,因为 $$$99 + 12 = 111$$$ 也是回文。
在第二个测试用例中 $$$1023 + 8646 = 9669$$$。
在第三个测试用例中 $$$385 + 604 = 989$$$。