题目描述

Zero 热衷于迷宫。Normal 的迷宫已经对他毫无吸引力了。

最近，他偶然发现一本叫做 Starcraft 的杂志上有一个（有奖）迷宫广告，这次他却停住了。这个 Abnomal 迷宫描述如下：一开始 Zero 会站在起点，他有 $n$ 点体力值。他可以选择向左或向右走或者不动，每个时刻最多只能走 $1$ 步，每一步消耗的体力为 $1$。两个时刻后，他就要被一种 Unknown 膜法带入另一个维度空间，此时，他还是能重复上述操作，但是每一次消耗的体力翻倍，如此下去，每过 $2$ 个时刻他都会被带入下一个维度空间内。由于迷宫的出口难以寻找，Zero 必须保证它在某个时刻恰好让体力消耗完（不可以降至负数），他才能拿到一个线索。并且只有当他找到所有可能的本质不同线索时，才能走出迷宫。两个线索本质不同的定义是：当且仅当存在一个维度空间内，两个线索对应的（行走方案）走的步数不一样，则称两个线索本质不同。

现在 Zero 找到了你，他非常需要这笔奖金，请你帮帮他算出有多少种可能的线索。由于线索数可能比较多，答案模 $10^9+7$ 后输出。

正当 Zero 觉得自己已经稳了的时候，发现万恶的 Starcraft 杂志又来刁难了，问题如下：

我们设 $f(n)$ 为体力为 $n$ 时本质不同的线索数且约定 $f(0)=1$。

Zero会受到一个询问，每个询问都是一个数对 $(p, q)$，需要找到最小的 $n$，使得 $\frac{f(n)}{f(n-1)}=\frac{p}{q}$。

由于答案可能会很大，请用输出描述给出的方式输出。

输入格式

本题有多组测试数据。第一行一个整数 $T$，代表数据组数。

接下来每一组数据各一行，三个整数 $n, p, q$，不保证 $p, q$ 互质，意义如题目中所示。

输出格式

对于每组测试数据，输出两行。

第一行对应前一个问题的答案，第二行对应后一个问题的答案。

对于第二个问题，输出一串数 $(x_1, x_2, x_3, ..., x_k)$ 来表示答案的二进制，即答案的二进制从高位到低位依次有 $x_1$ 个 $1$，$x_2$ 个 $0$，$x_3$ 个 $1$，……，$x_{2i}$ 个 $0$，$x_{2i+1}$ 个 $1$，……，$x_k$ 个 $(k \ \text{and} \ 1)$。

保证输出的所有数都在 long long 范围内。

6
1 1 1
2 2 5
3 3 9
4 4 13
5 5 17
19260817 2333 6666

1
(1)
2
(1,1,2)
1
(3)
3
(1,3,3)
2
(2,2,3)
21035
(2,166,6,1,2)

数据范围与提示

对于全部数据，$1\le T\le 10^4,1 \leq n, p, q \leq 10^{18}$。