Online Programming Server

Real enjoys walking up staircase As he moves up, he either takes one or two steps at a time (See the figure for clarification.) Recently, he attended an ACM training instructed by PP, and realized a funny fact: if there are N steps in the staircase, the number of ways he could finish walking up is exactly the N^th Fibonacci number! Real is interested in all possible ways he can walk up the staircase. Please help him.

The first line contains an integer T(1 ≤ T ≤ 20), the number of test case. For each of the following T lines, each line contains an integer, N (1 ≤ N ≤ 20), specifying the number of steps of the staircase.

For each test case, output each possible way of walking up the staircase. Each way should be printed on a line as a sequence of 1s and/or 2s, separated by space. (i.e., there is no space character at the end of each line) If there are multiple ways, output them in lexicographical order. Output a line consisting a `#' after each test case.