#1503. 迷宫

迷宫

题目描述

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

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

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

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

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

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

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

输入格式

本题有多组测试数据。第一行一个整数 TT,代表数据组数。

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

输出格式

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

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

对于第二个问题,输出一串数 (x1,x2,x3,...,xk)(x_1, x_2, x_3, ..., x_k) 来表示答案的二进制,即答案的二进制从高位到低位依次有 x1x_111x2x_200x3x_311,……,x2ix_{2i}00x2i+1x_{2i+1}11,……,xkx_k(k and 1)(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)

数据范围与提示

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