P11063 [MX-X4-T3] "Jason-1" Pair Transformation.

Original problem link: .

For a pair of **positive integers** $(x, y)$, define one transformation as follows: choose one number $a$, let the other number be $b$, and at the same time choose a positive integer $k \leq a$. Then divide $a$ by $k$ and take the floor, and multiply $b$ by $k$. Formally, for the pair $(x, y)$, you may perform the following two types of transformations: - Type 1: choose $1 \le k \le x$, set $(x,y) \gets (\lfloor \frac{x}{k} \rfloor, y \cdot k)$. - Type 2: choose $1 \le k \le y$, set $(x,y) \gets (x \cdot k, \lfloor \frac{y}{k} \rfloor)$. Obviously, the resulting pair is still a pair of positive integers. Given two pairs of positive integers $(a, b)$ and $(c, d)$, you need to perform **no more than $\bm{65}$** transformations to change $(a, b)$ into $(c, d)$, or report that there is no solution. **Note: you do not need to minimize the number of transformations.** Note that the pair is ordered, i.e., if $x \neq y$, then $(x,y) \neq (y,x)$. This problem uses a **custom checker** to verify whether your answer is correct, so if there are multiple valid solutions, you only need to output **any one** of them.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case: - One line with four positive integers $a, b, c, d$, representing the two pairs.

For each test case: - If there is no solution, - output one line with the string `-1`. - Otherwise, - the first line contains a non-negative integer $m$, the number of transformations you perform. **You must ensure $\bm{0 \le m \le 65}$, but you do not need to minimize $\bm m$**. - The next $m$ lines: the $i$-th line contains two integers $\mathit{op}, k$, representing the $i$-th transformation. Here $\mathit{op} \in \{1, 2\}$ indicates the transformation type, and $k$ is the chosen $k$ in this transformation. This problem uses a **custom checker** to verify whether your answer is correct, so if there are multiple valid solutions, you only need to output **any one** of them.

**[Sample Explanation]** For test case 1, no operation is needed because initially $a = c$ and $b = d$. For test case 2, it can be proven that there is no solution. For test case 3, after the first transformation $(a,b)=(1,4)$, after the second transformation $(a,b)=(3,1)$, and after the third transformation $(a,b)=(1,2)$. For test case 4, one transformation is enough to make $a = c$ and $b = d$. For test case 5, it can be proven that there is no solution. For test case 6, after the first transformation $(a,b)=(26,129)$, and after the second transformation $(a,b)=(52,64)$. For test case 7, after the first transformation $(a,b)=(31438,3878395026435)$, and after the second transformation $(a,b)=(313814116,388538872)$. **[Constraints]** **This problem uses bundled testdata.** Let $n=\max(a,b,c,d)$. | Subtask | $n\le$| Special Property | Score | | :--------------: | :-----: |:-----:| :--------: | | 1 | $6$ | None | $7$ | | 2 | $10^5$ | A | $11$ | | 3 | $10^5$ | C | $13$ | | 4 | $10^6$ | B | $23$ | | 5 | $10^9$ | C | $19$ | | 6 | $10^9$ | None | $27$ | - Special Property A: guaranteed $\dfrac{a}{c}=\dfrac{d}{b}$. - Special Property B: guaranteed $a=b$ and $c=d$. - Special Property C: guaranteed that $a,b,c,d$ are generated independently and uniformly at random within the value range. For $100\%$ of the testdata, $1 \le T \le 10^4$, $1 \le a,b,c,d \le 10^9$. Translated by ChatGPT 5