
ZOJ Problem Set  3951
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. InputThere 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). OutputFor 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. Sample Input5 1 2 3 10 20 Sample Output1 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 