World Cup Noise

Interview

Time limit1sMemory limit128 MB

Summary

For each n below 45, count the n-bit strings that contain no two adjacent 1s, and print the result per scenario with a blank line between cases.

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

Problem

"KO-RE-A, KO-RE-A!" chant 54,000 happy football fans after their national team reaches the World Cup semifinals on home soil. The fans want to keep the noise level constant throughout the match, so they bring in huge trumpets (powered by compressed gas) that blare like a ship's horn.

There is one catch: if a trumpet is blown for 2 seconds without stopping, it breaks. So the fans agree on a chanting pattern — a sequence of 0s and 1s read as follows:

1 means the trumpet is blown.
0 means the fans chant "KO-RE-A" instead.

To make sure no trumpet breaks, the pattern must never contain two consecutive 1s.

Given a positive integer $n$ , determine how many different chanting patterns of length $n$ are possible — that is, the number of $n$ -bit sequences with no two adjacent 1s. For example, for $n = 3$ the answer is 5: the sequences 000, 001, 010, 100, 101 are allowed, while 011, 110, 111 are not.

Input

The first line contains the number of scenarios.

Each of the following lines contains a single positive integer $n$ ( $1 \le n < 45$ ), one per scenario.

Output

For each scenario, first print a line "Scenario #i:", where $i$ is the scenario number starting from 1. On the next line, print the number of $n$ -bit sequences that have no two adjacent 1s. Separate consecutive scenarios with a blank line.

Examples4

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

Scenario #2:
2
```
Example 2
Input
```
1
1
```
Expected output
```
Scenario #1:
2
```
Example 3
Input
```
1
2
```
Expected output
```
Scenario #1:
3
```
Example 4
Input
```
1
3
```
Expected output
```
Scenario #1:
5
```