SP3922 BYTESM1 - Mystical River

哈利·波特因为鲁莽被斯内普处罚，被送去禁林留校察看。现在他在森林中迷路了，遇到三条神秘的河流，却不确定该跨过哪条才能回到学校。每条河流的岸边每隔一米有一块石头，上面标有一个数字。三条河流的起始数字分别是 1、3 和 9。每块石头上的数字等于前一块石头上的数字加上该数字各位数之和。举例来说，如果某个石头上的数字是 403，下一个则是 403 + 4 + 0 + 3 = 410，再下一个是 410 + 4 + 1 + 0 = 415，依此类推。哈利把这种石头上的连续数字称作“石河”。 哈利知道，他需要在他记得的数字 $N$ 所生成的“石河”与河流 1、3 或 9 之一的“石河”相交的石头位置过河。你的任务是帮助哈利找到他的记忆数字 $N$ 所对应的“石河”与这些神秘河流的交点。如果有多个交点，我们选择最小的那个。例如，如果哈利记得的数字是 29，那么在 107 这个位置的石头上两条“石河”相交，他需要在这里过河，因为 107 也出现在数字 1 的“石河”中。29 的“石河”是 29, 40, 44, 52, 59, 73, 83, 94, 107, ……；而 1 的“石河”是 1, 2, 4, 8, 16, 23, 28, 38, 49, 62, 70, 77, 91, 101, 103, 107, ……。因此，哈利需要在 107 这个石头上过河。

输入的第一行为一个整数 $T$（$1 \le T \le 50$），表示测试用例的数量。接下来的 $T$ 行中，每行包含一个整数 $N$（$1 \le N \le 99999999$），代表哈利记得的数字。

共 $T$ 行，每行输出两个整数，用空格隔开。第一个整数表示与 $N$ 的“石河”相交的神秘河流（1、3 或 9）。第二个整数表示哈利可以过河的石头编号。 **本翻译由 AI 自动生成**