Encoding

Interview

Time limit1sMemory limit128 MB

Summary

Count binary strings of length n that start with 1 and contain no adjacent ones for up to 100 queries.

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

Problem

Paweł, a computer science student, became fascinated by the problems covered in his data compression course last semester. Being a keen student, he decided to invent a new way to compress sequences of natural numbers.

The first step of Paweł's algorithm is to turn a sequence of natural numbers into a sequence of numbers written in binary. You cannot simply concatenate them: using only zeros and ones, you must still be able to tell where one encoded number ends and the next begins. To do this, Paweł decided to use two adjacent ones as the marker for the end of a single number. This choice has consequences. So that consecutive elements can be separated, the binary code of any number must not contain two adjacent ones, and it must start with a one.

To study how well the compression works, Paweł needs to know how many different numbers he can encode using n bits. Your task is to write a program that, for a given value n, computes how many different binary codes of length n start with a one and do not contain two adjacent ones.

Input

The first line contains one integer T (1 ≤ T ≤ 100), the number of data sets. Then the data sets follow. Each data set consists of a single line containing one integer n (1 ≤ n ≤ 45).

Output

For each data set, print a single line containing one integer: the number of different binary strings of length n that start with a one and do not contain two adjacent ones.

Hint

The strings of length 4 that satisfy the criteria are 1000, 1001, 1010.

Examples4

Example 1
Input
```
2
1
4
```
Expected output
```
1
3
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
5
```
Expected output
```
5
```
Example 4
Input
```
5
1
2
3
4
5
```
Expected output
```
1
1
2
3
5
```