인코딩

정보를 공부하는 학생 파벨은 지난 학기에 들은 자료 압축 수업에서 다룬 문제들에 흥미를 느꼈다. 그는 자연수 수열을 압축하는 새로운 방법을 고안하기로 했다.

파벨이 만든 알고리즘의 첫 단계는 자연수들의 수열을 이진수로 표현한 수열로 바꾸는 것이다. 그런데 단순히 이어 붙이기만 하면 어디서 한 수가 끝나고 다음 수가 시작되는지 알 수 없다. 0과 1만으로 각 수의 경계를 구분해야 하므로, 파벨은 연속한 두 개의 1을 한 수의 끝을 나타내는 구분자로 쓰기로 했다. 이 규칙 때문에 하나의 수를 나타내는 이진 코드에는 다음 제약이 생긴다: 코드 안에 1이 두 개 연속으로 나올 수 없고, 코드는 반드시 1로 시작해야 한다.

압축 효율을 알아보기 위해, 파벨은 n개의 비트로 서로 다른 코드를 몇 개나 만들 수 있는지 알고 싶어 한다. 주어진 n에 대해, 길이가 n이면서 1로 시작하고 1이 두 개 연속으로 나오지 않는 서로 다른 0-1 문자열의 개수를 구하는 프로그램을 작성하여라.

첫째 줄에 데이터 집합의 개수 T (1 ≤ T ≤ 100)가 주어진다. 이어서 T개의 데이터 집합이 주어진다. 각 데이터 집합은 한 줄로 이루어지며, 그 줄에는 정수 n (1 ≤ n ≤ 45)이 하나 주어진다.

각 데이터 집합마다, 길이가 n이면서 1로 시작하고 1이 두 개 연속으로 나오지 않는 서로 다른 0-1 문자열의 개수를 한 줄에 하나씩 출력한다.

길이가 4이면서 조건을 만족하는 문자열은 1000, 1001, 1010 세 가지이다.