World Cup Noise

"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.

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.

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.