A Very Nasty Graph Problem

Why do statements of programming olympiad problems always come with such absurd adventures, packed with all sorts of ridiculous events? I would like to write this problem's statement that way too. But it is clear that the story I want to write right now is too big to fit on this small piece of paper. So, "Shall I keep writing? What should I do?" It is quite interesting, actually. Can I promise that once you start reading, you will forget about solving the problem and read to the end with enjoyment? What is this story to make such a fuss? Which matters more, the problem or the story? Are you thinking about which one to choose? "So many questions. Just ask one thing." :)) Or are you thinking that this story is nonsense, that it rambles on with too many pointless words? Why not just write the real statement properly and get on with your work? "Well, whatever. Everyone does it that way."

Problem summary in statement: Print the shortest string that contains every N-digit binary number, and among those, the lexicographically smallest one.

The first line contains the number of tests T (T ≤ 15). Each of the next lines contains the number of digits N (N ≤ 15) representing one test.

For each test, print the corresponding answer on a new line.

To make a binary number N digits long, it starts with 0. For example, listing all 3-digit binary numbers gives 000, 001, 010, 011, 100, 101, 110, 111, and the shortest string containing all of them that is lexicographically smallest is 0001011100.