P11156 [MX-X6-T2] Moshimo

Original problem link: 。 --- > _もしも$\\$ 数字がない世界だったら$\\$ 生きる期限なんて$\\$ なかったのかな$\\$ もしもの話なら良かった$\\$ また出逢えるからって$\\$ 言うんだ$\\$ またね。_ > >_—— [もしも - Nanatsukaze / Dankidz](https://music.163.com/#/song?id=2102257032)_ Can division help us erase the numbers in this world? If not, can we meet again?

Suppose there is a positive integer sequence $a_1, a_2, \ldots, a_n$, where: - For $i \ge 3$, $a_i$ equals $\dfrac{a_{i-2}}{a_{i-1}}$ rounded up; - For any $1 \le i \le n$, $1 \le a_i \le 10^9$. Now given $n$ and $a_n$, find any possible pair $a_1, a_2$. Rounding up a number $x$ means the smallest integer $\ge x$. For example, $\dfrac{7}{3}$ rounded up equals $3$, and $4$ rounded up equals $4$.

Each test point contains multiple sets of testdata. The first line contains an integer $T$, the number of test cases. Then follow $T$ lines. Each line contains two integers separated by a space, representing $n, a_n$ for that test case.

For each test case, output one line with two integers, representing one possible pair $a_1, a_2$. If there are multiple solutions, output any one. It can be proven that within the constraints of this problem, a solution always exists.

**Sample Explanation** For the three test cases, the sequences are: - $a=[114,514,1]$； - $a=[2005,1130,2]$； - $a=[59001,897,66,14,5,3]$。 **Constraints** For all testdata, $1 \le T \le 1000$, $3 \le n \le 10^9$, $1 \le a_n \le 10^9$. There are $10$ groups of testdata in total: - For the first $2$ groups, additionally $n \le 6$, $a_n \le 10$； - For the first $5$ groups, additionally $n \le 1000$； - For groups $6$ and $7$, additionally $a_n = 1$。 Translated by ChatGPT 5