当你自信满满地把你认为的正确密码输入后，时光机滴滴报警 —— 密码错误。你摊坐在了地上。

黑衣人满意地拍了拍你的肩膀：“小伙子，不错嘛。虽然没解开密码，但是离解开密码也不远咯。其实刚才是个对你的考验。来加入我们保护星期日委员会吧！”

你惊讶得从地上直接 splay 了起来：“就是那个传说中的保护星期日委员会？咦，那为什么今天星期日还要上学呢？”

黑衣人：“你不是高三学生吗？”，你一脸无语。黑衣人又说道：“小伙子跟我干吧，我们一起去摧毁 IIIS。”

于是你们跋山涉水来到了 IIIS 基地的一个秘密仓库门前。duang地一下放倒了门卫之后你们试图开门窃取秘密资料。可是这个门装备了最新的智商锁，只有你的智商恰好等于锁的主人门才会打开。于是门上出现一道迷题：

给你一个 $k$，请你构造一个结点数不超过 $100$ 的无向图，使得这个无向图中生成树的个数对 $998244353$（$7\times 17\times 2^{23}+1$，一个质数）取模后恰为 $k$。

作为智商超高的你一定一眼秒掉了此题！请写一个程序证明你的智商跟智商锁的主人一样吧！

输入格式

第一行一个正整数 $T$。

接下来 $T$ 行每行一个非负整数 $k$，保证 $0\le k<998244353$。

输出格式

你需要对每一个给出来的 $k$，输出一张无自环无重边的无向图。如果有多解输出任意一组解均可。如果无解请输出卖萌表情 “QwQ”（不含引号）。

输出无向图时，先一行两个非负整数 $n,m$，分别表示结点数和边数。你需要满足 $1\le n\le 100$。接下来 $m$ 行，每行两个整数 $v,u$ 表示 $v$ 号结点和 $u$ 号结点之间有一条无向边。结点从 $1$ 到 $n$ 编号。

样例一

input

2
8
16

output

4 5
1 2
1 4
2 4
2 3
3 4
4 6
1 2
1 4
2 4
2 3
3 4
1 3

explanation

样例输出的两个图分别如下：

1---4     1---4
|  /|     |\ /|
| / |     | x |
|/  |     |/ \|
2---3     2---3

左图中，2 到 4 这条边在生成树上有 $4$ 种方案，不在生成树上又有 $4$ 种方案。所以共有 $8$ 棵生成树。

右图有 $16$ 棵生成树。

样例二

见样例数据下载。

限制与约定

对于所有数据，$T\le 10$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载