Time Limit: 1 Second
Memory Limit: 65536 KB
Chiaki has a positive integer m and she would like to construct a tree with at most 15 vertices in such a manner that the number of distinct nonempty independent sets is exactly m.
Note that an independent set is a subset of vertices of a graph such that every two distinct vertices are not adjacent.
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 2000), indicating the number of test cases. For each test case:
The first line contains an integer m (1 ≤ m ≤ 2000).
For each test case, if there is no such graph, output -1 on a single line. Otherwise, output an integer n (1 ≤ n ≤ 15) denoting the number of vertices. Then in each of the next n - 1 lines, output two integers x and y (1 ≤ x, y ≤ n, x ≠ y) denoting an edge in the tree.