Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3951
Independent Set

Time Limit: 1 Second      Memory Limit: 65536 KB      Special Judge

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.

#### Input

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).

#### Output

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, yn, xy) denoting an edge in the tree.

```5
1
2
3
10
20
```

#### Sample Output

```1
2
2 1
-1
-1
6
2 1
3 1
4 3
5 4
6 5
```

Author: LIN, Xi
Source: The 17th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status