题目描述

对于一个正整数数对 $(x, y)$，定义一次变换为：选择其中一个数 $a$，记另一个数为 $b$，同时选择一个正整数 $k \leq a$，然后将 $a$ 除以 $k$ 向下取整，同时将 $b$ 乘以 $k$。

形式化地说，对于数对 $(x,y)$，你可以执行以下两种变换：

• 类型 1：取 $1 \le k \le x$，令 $(x,y) \gets (\lfloor \frac{x}{k} \rfloor, y \cdot k)$。
• 类型 2：取 $1 \le k \le y$，令 $(x,y) \gets (x \cdot k, \lfloor \frac{y}{k} \rfloor)$。

显然，变换后的数对仍然是正整数数对。

给出两组正整数数对 $(a, b)$ 与 $(c, d)$，你需要执行不超过 $\bm{65}$ 次变换将 $(a, b)$ 变为 $(c, d)$，或者报告无解。注意：你不需要最小化执行变换的次数。

需要注意数对是有序的，即若 $x \neq y$，则 $(x,y) \neq (y,x)$。

本题使用自定义校验器检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出任意一种。

输入格式

本题输入包含多组数据。

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

• 仅一行，四个正整数 $a, b, c, d$，表示两组数对。

输出格式

对于每组数据：

• 若无解，
  • 仅一行一个字符串 -1。
• 否则，
  • 第一行，一个非负整数 $m$，表示你执行变换的次数。你需要保证 $\bm{0 \le m \le 65}$，但不需要最小化 $\bm m$。
  • 接下来 $m$ 行，第 $i$ 行两个整数 $\mathit{op}, k$，表示你执行的第 $i$ 次变换。其中 $\mathit{op} \in \{1, 2\}$ 表示变换类型，$k$ 即为本次变换中选择的 $k$。

本题使用自定义校验器检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出任意一种。

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

提示

【样例解释】

对于第 1 组数据，不需要进行任何操作，因为初始时 $a = c$ 且 $b = d$。

对于第 2 组数据，可以证明无解。

对于第 3 组数据，第一次变换后 $(a,b)=(1,4)$，第二次变换后 $(a,b)=(3,1)$，第三次变换后 $(a,b)=(1,2)$。

对于第 4 组数据，一次变换即可使 $a = c$ 且 $b = d$。

对于第 5 组数据，可以证明无解。

对于第 6 组数据，第一次变换后 $(a,b)=(26,129)$，第二次变换后 $(a,b)=(52,64)$。

对于第 7 组数据，第一次变换后 $(a,b)=(31438,3878395026435)$，第二次变换后 $(a,b)=(313814116,388538872)$。

【数据范围】

本题采用捆绑测试。

令 $n=\max(a,b,c,d)$。

子任务	$n\le$	特殊性质	分值
1	$6$	无	$7$
2	$10^5$	A	$11$
3		C	$13$
4	$10^6$	B	$23$
5	$10^9$	C	$19$
6		无	$27$

• 特殊性质 A：保证 $\dfrac{a}{c}=\dfrac{d}{b}$。
• 特殊性质 B：保证 $a=b$ 且 $c=d$。
• 特殊性质 C：保证 $a,b,c,d$ 在值域内独立均匀随机生成。

对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le a,b,c,d \le 10^9$。