Background

Original problem link: https://oier.team/problems/X4D.

Problem Description

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.

Input Format

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.

Output Format

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.

7
1 1 1 1
1 2 1 1
2 2 1 2
10 10 2 50
5 5 4 10
80 43 52 64
987654321 123456789 313814116 388538872

0
-1
3
1 2
2 3
1 2
1
1 5
-1
2
1 3
2 2
2
1 31415
2 9982

Hint

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

• 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