문제
Fi-binary 수는 0 과 1 로만 이루어진 숫자이다.
이 숫자는 앞에 0 이 붙지 않으며, 2개의 연속된 1 이 나타나지 않는 숫자이다.
이 숫자를 크기 순 으로 늘어놓으면 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101... 와 같다.
n이 주어졌을 때 n번째 Fi-binary 숫자를 찾는 프로그램을 작성하라.
입력
첫 번째에는 테스트 케이스의 개수 T가 주어진다(T≤10,000).
두 번째 줄부터 T개의 줄에는 찾고자 하는 Fi-binary 숫자의 순서 n(1≤n≤109)이 주어진다.
출력
각각의 테스트 케이스에 대해 n번째의 Fi-binary 숫자를 출력한다.
예제1
입력
4
10
20
30
40
출력
10010
101010
1010001
10001001
출처
uva 11089 - Fi-binary Number