暑假到了，Gealo也不能因为放假而懈怠刷题于是....Gealo决定出去玩一下♪(´ε｀ )，但是一不小心被Olaeg抓住了。Olaeg不是个无情的人所以当然是....不放过他啊。Olaeg出了一道题目給Gealo除非他解决这题否则别想出去玩。
当然像Gealo这么机智的人肯定能够解决这个问题的，所以拜托你们帮他解决一下这个问题(╯﹏╰）（在线等）
问题是这样的一串字符串只有0，1组成而且两个1不能相邻，问按照字典序排下来第n个字符串是什么，例如1～7个是1，10，100，101，1000，1001，1010

第一行一个t表示组数（t<=10000）
每组一个n（1<n<10^9）

输出对应的字符串