题目描述

NIO has a tree $T$ rooted at $1$.

He defines the hash function of $T$ as $F(T)=\left(\sum\limits_{i=1}^n\sum\limits_{j=i+1}^{n}X^iY^jZ^{\text{lca}(i,j)}\right)\bmod P$, where $P = 998244353$ and $\text{lca}(i,j)$ is the lowest common ancestor of $i$ and $j$.

Unfortunately, he lost the tree in an accident. The only thing he remembers is $F(T)$.

Now given $F(T)$ and $X,Y,Z$, you need to reconstruct $T$ with no more than $50$ vertices.


输入格式

The first line contains an integer $T\ (1\leq T\le 20)$ indicating the number of test cases.

For each test case, the only line contains four integers $F(T),X,Y,Z\ (0\le F(T)< P, 2\le X,Y,Z\le P - 2)$.

It is guarenteed that $X,Y,Z$ are chosen randomly from range $[2, P - 2]$.


输出格式

For each test case, output $n$ lines, where $n$ is the number of vertices of the tree.

The first line output $n$. You should make sure that $1\le n\le 50$.

The next $n-1$ lines output two integers $u, v\ (1\leq u, v \leq n, u\neq v)$ indicating an edge in your tree. These $n - 1$ edges should form a tree.


样例数据

输入

1
36 2 3 2

输出

2
1 2

备注


操作

评测记录

优秀代码

信息

时间限制: 7s
内存限制: 256MB
评测模式: Normal

题解