월드컵 함성

홈에서 열린 월드컵 4강에 자국 대표팀이 진출하자 5만 4천 명의 축구 팬이 "KO-RE-A, KO-RE-A"를 외친다. 팬들은 경기 내내 응원 소리의 크기를 일정하게 유지하고 싶어 한다. 그래서 배의 경적처럼 큰 소리를 내는 거대한 나팔(압축 가스로 작동)을 준비했다.

문제가 하나 있다. 나팔을 쉬지 않고 2초 동안 불면 고장 난다. 그래서 팬들은 응원 패턴을 정하기로 했다. 응원 패턴은 다음과 같이 해석되는 0과 1의 수열이다.

• 1이면 나팔을 분다.
• 0이면 나팔 대신 팬들이 "KO-RE-A"를 외친다.

나팔이 고장 나지 않으려면 패턴에 1이 연속으로 두 번 나오면 안 된다.

양의 정수 $n$이 주어질 때, 길이가 $n$인 서로 다른 응원 패턴의 개수, 즉 연속한 두 개의 1이 없는 $n$비트 수열의 개수를 구하여라. 예를 들어 $n = 3$일 때 답은 5이다. 수열 000, 001, 010, 100, 101은 허용되지만 011, 110, 111은 허용되지 않는다.

첫째 줄에 시나리오의 개수가 주어진다.

이어지는 각 줄에는 시나리오마다 45보다 작은 양의 정수 $n$이 하나씩 주어진다 ($1 \le n < 45$).

각 시나리오에 대해 먼저 "Scenario #i:"를 한 줄에 출력한다. 여기서 $i$는 1부터 시작하는 시나리오 번호이다. 다음 줄에는 연속한 두 개의 1이 없는 $n$비트 수열의 개수를 출력한다. 연속한 두 시나리오 사이는 빈 줄로 구분한다.