Prehistoric Operating Systems

Interview

Time limit1sMemory limit128 MB

Summary

Count binary strings of length n with no two adjacent D's, where D means DOORS and O means any other brand, for up to 40 test values of n.

Level: Easy3 of 10
Topics: Dynamic programming, Combinatorics, Math, Array
Solved: No attempts yet

Problem

It is the year 2254. Ohio Smith is a specialist in ancient operating systems. For his research he wants to install several operating systems, used about 250 years ago, on a single computer.

Earlier research showed that the order in which these ancient operating systems are installed usually does not matter. One brand, however, the DOORS OS, has a peculiar quirk: two versions of DOORS can never be installed one right after another. Between any two DOORS installations there must be at least one operating system of a different brand.

Ohio wants to install exactly $n$ operating systems, choosing for each installation slot either DOORS or some other operating system. Count how many different valid installation sequences he can form.

Input

The first line contains the number of scenarios.

Each scenario is given on its own line as a single integer $n$ ( $1 \le n \le 40$ ), the number of operating systems to install.

Output

For each scenario, print a line Scenario i:, where $i$ is the scenario number starting from 1, followed by a line containing the number of valid installation sequences. Print a blank line between consecutive scenarios.

Hint

For $n = 3$ there are 5 valid ways to install the operating systems (D = DOORS, O = other):

D, O, O
O, O, O
O, O, D
O, D, O
D, O, D

Examples2

Example 1
Input
```
2
3
9
```
Expected output
```
Scenario 1:
5

Scenario 2:
89
```

Example 2

Input

Expected output

Scenario 1:
2

Scenario 2:
3

Scenario 3:
5

Scenario 4:
8