Background

Original problem link: https://oier.team/problems/X6C。

もしも$\\$ 数字がない世界だったら$\\$ 生きる期限なんて$\\$ なかったのかな$\\$ もしもの話なら良かった$\\$ また出逢えるからって$\\$ 言うんだ$\\$ またね。

—— もしも - Nanatsukaze / Dankidz

Can division help us erase the numbers in this world?

If not, can we meet again?

Problem Description

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$.

Input Format

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.

Output Format

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.

3
3 1
3 2
6 3

114 514
2005 1130
59001 897

Hint

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