선사 시대 운영체제

때는 2254년. 오하이오 스미스(Ohio Smith)는 고대 운영체제를 연구하는 전문가이다. 그는 연구를 위해 약 250년 전에 쓰이던 여러 운영체제를 한 대의 컴퓨터에 설치하려고 한다.

이전 연구에 따르면 이런 고대 운영체제들은 대부분 설치 순서가 결과에 영향을 주지 않는다. 그런데 'DOORS'라는 브랜드의 운영체제에는 독특한 제약이 있다. DOORS는 두 버전을 연속으로 설치할 수 없어서, 두 DOORS 설치 사이에는 반드시 다른 브랜드의 운영체제가 하나 이상 설치되어 있어야 한다.

오하이오는 정확히 $n$개의 운영체제를 설치하려고 하며, 각 설치 자리마다 DOORS 또는 다른 운영체제 중 하나를 고른다. 만들 수 있는 서로 다른 유효한 설치 순서의 개수를 구하여라.

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

각 시나리오는 한 줄에 설치할 운영체제의 개수 $n$ ($1 \le n \le 40$)이 정수로 주어진다.

각 시나리오마다 먼저 Scenario i: 형식의 줄을 출력한다. 여기서 $i$는 1부터 시작하는 시나리오 번호이다. 그다음 줄에 유효한 설치 순서의 개수를 출력한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 출력한다.

$n = 3$일 때 운영체제를 설치하는 유효한 방법은 5가지이다 (D = DOORS, O = 다른 운영체제):

1. D, O, O
2. O, O, O
3. O, O, D
4. O, D, O
5. D, O, D