P11436 [Code+#8 决赛] 生成树

搬运自 [Code+ #8 决赛](https://gitlink.org.cn/thusaa/codeplus8final)。

小 I 既喜欢生成树，又喜欢他的幸运数字 $k$，所以小 I 想造出一个**可以有重边自环**的有向图，点从 $1$ 到 $n$ 编号，使得以 $1$ 为根的**外向**生成树数量**恰好**为 $k$。但小 I 太穷了，手边只有 100 条有向边，所以他请求你的帮助，请你帮他造出这样的一个有向图，或者告诉他这是不可能的。

**本题有多组测试数据。** 输入的第一行包含一个正整数 $q$，表示询问次数。接下来 $q$ 行每行包含一个正整数 $k$，描述一次询问。

对于每次询问，若不存在方案，只需要输出一行一个整数 `-1`。否则输出多行：第一行两个整数 $n,m$，分别表示你给出的有向图的点数和边数，你需要保证 $1 \le n \le 101, 0 \le m \le 100$。接下来 $m$ 行，第 $i$ 行两个整数 $u_i,v_i$，表示一条从 $u_i$ 到 $v_i$ 的有向边。你需要保证 $1 \le u_i, v_i \le n$。

**【数据范围】** 对于所有数据，$1 \le q \le 100$，$1 \leq k \le 7 \times 10^{15}$。 本题采用 $\text{Subtask}$ 捆绑测试。 |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$3$|$k\le100$| |$2$|$7$|存在整数 $0 \le a,b \le 20$ 使得 $k = 2^a3^b$| |$3$|$10$|$q=1, k = 101$| |$4$|$10$|$k \le 10^3$| |$5$|$7$|$k \le 10^4$| |$6$|$7$|$k \le 10^6$| |$7$|$8$|$k \le 3 \times 10^7$| |$8$|$8$|$k \le 8 \times 10^9$| |$9$|$10$|$k \le 10^{12}$| |$10$|$10$|$k \le 3 \times 10^{14}$| |$11$|$20$|$k \le 7 \times 10^{15}$|