P15818 [HackerEarth] Raju has recently learnt converting a binary string into a decimal number. Raju likes this base conversion very much but he doesn't like binary strings that contain substrings having odd
普及
题目描述

Raju has recently learnt converting a binary string into a decimal number. Raju likes this base conversion very much but he doesn't like binary strings that contain substrings having odd number of contiguous 1's. Help Raju to find the total number of decimal numbers that can be generated from a binary string of length L that does not contain substrings having odd number of contiguous 1's.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains a single line denoting the length L of the binary string.

Output

Output contains T lines, each line denoting the number of all possible binary strings of respective length.

Constraints
1 ≤ T ≤ 1000
1 ≤ L ≤ 40

SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
1
2

Explanation

Example case 1. Only one decimal number {0} is possible having binary equivalent '0'.
Example case 2. Two decimals {0, 3} having binary equivalents {'00','11'} respectively are possible.

输入格式

见题面

输出格式

见题面

样例输入
1000 27 11 12 15 15 16 13 37 28 6 32 39 23 27 1 5 29 14 21 1 13 10 12 24 14 1 3 39 39 24 12 24 23 1 22 4 3 27 15 5 12 36 7 31 5 7 9 37 32 14 21 19 15 4 29 2 2 31 4 22 6 37 1 35 28 23 21 3 12 17 13 29 1 30 5 20 14 13 13 2 6 21 3 6 22 21 16 39 14 7 39 20 9 8 2 31 9 22 39 34 38 4 40 30 11 17 16 30 7 4 39 6 31 9 31 27 27 21 19 8 8 22 26 11 37 34 13 32 32 12 18 16 1 5 18 38 22 31 22 6 1 28 39 8 3 23 37 30 25 18 16 24 1 29 20 36 28 25 31 7 5 36 26 18 7 32 32 22 31 25 34 19 37 22 20 15 31 11 3 15 37 40 37 38 2 3 20 14 37 18 32 31 38 40 5 29 14 12 8 6 28 35 25 12 30 17 33 2 39 33 30 17 26 18 7 39 1 25 27 8 14 30 37 9 12 10 10 28 29 1 2 36 29 37 27 25 29 31 37 39 18 35 29 20 20 38 38 29 40 28 25 15 26 37 26 13 30 30 18 22 3 7 20 5 35 4 7 35 10 17 27 38 5 36 7 37 4 17 16 3 22 18 21 17 17 7 29 31 16 36 23 13 2 21 6 33 2 28 24 11 38 17 2 18 2 10 15 2 26 14 34 30 1 1 10 31 15 18 21 36 19 15 30 15 4 23 3 34 22 38 39 5 34 7 29 31 14 3 17 35 30 1 37 7 13 26 25 14 23 29 29 40 31 21 5 1 11 32 3 36 31 20 19 30 3 34 35 10 22 39 18 31 18 1 37 2 25 7 13 23 11 20 9 23 1 33 11 19 19 11 3 6 11 35 5 15 18 1 7 32 9 20 31 25 28 34 17 27 26 34 21 12 29 24 13 5 21 26 23 3 2 19 39 37 40 18 34 14 27 19 5 26 26 5 28 2 34 38 4 2 38 7 6 13 15 5 7 36 5 15 34 25 14 12 22 23 29 17 28 31 23 17 25 16 2 18 6 40 21 33 36 32 20 8 13 37 11 29 13 8 18 26 16 7 30 21 28 33 36 15 17 5 22 35 30 15 31 23 34 22 28 22 13 21 29 2 34 29 27 6 35 27 9 37 9 35 40 7 1 4 26 24 8 10 19 9 32 38 38 31 25 1 6 17 5 18 18 22 10 37 1 39 16 38 5 11 15 9 17 21 14 13 36 8 26 27 25 9 23 22 7 14 38 7 34 38 5 8 15 10 33 19 2 23 22 25 22 15 31 18 38 5 40 35 2 2 6 3 2 40 38 19 30 37 36 34 40 40 12 37 29 29 5 37 9 19 26 16 38 32 2 6 33 2 30 31 22 8 10 38 2 21 26 13 34 31 3 28 1 10 8 26 1 37 19 3 15 31 25 16 6 28 35 14 39 21 21 6 2 18 22 30 39 10 15 19 7 19 39 14 39 39 20 31 13 38 39 10 26 38 7 34 6 14 13 23 17 31 40 38 24 10 27 39 11 37 38 31 28 36 28 25 1 34 37 2 20 3 23 23 22 32 10 3 38 17 24 13 1 2 26 37 3 30 21 32 27 31 1 29 31 11 23 4 19 11 10 20 37 38 18 25 21 35 23 21 33 6 39 29 20 38 1 32 3 7 31 28 37 36 32 25 19 27 15 37 28 28 34 38 15 2 32 12 19 28 32 9 29 35 3 19 19 1 3 32 31 17 28 22 15 35 1 5 1 28 25 38 20 17 3 17 2 16 19 39 29 35 18 16 38 35 9 3 5 22 4 10 12 38 7 30 3 26 17 1 33 13 6 35 35 21 11 4 1 24 15 32 7 30 21 18 7 14 8 7 35 25 23 28 4 32 36 34 4 27 5 12 13 4 38 39 24 40 36 14 37 2 27 13 27 37 40 40 20 32 8 12 10 22 17 39 34 1 38 6 1 12 21 14 16 21 8 31 22 9 31 6 27 14 21 18 28 28 37 13 40 19 1 31 9 11 22 30 13 10 21 35 30 16 12 22 38 34 27 8 36 30 30 20 28 5 39 16 14 30 20 3 14 10 20 36 26 14 21 7 28 24 40 10 21 10 30 39 29 31 10 31 33 5 26 19 13 37 1 12 13 8 18 4 32 21 12 15 36 34 24 36 3 26 8 1 6 26 12 22 12 33 31 12 10 3 9 6 14 20 4 22 19 36 34 23 15 29 30 2 40 34 38 13
样例输出
317811 144 233 987 987 1597 377 39088169 514229 13 3524578 102334155 46368 317811 1 8 832040 610 17711 1 377 89 233 75025 610 1 3 102334155 102334155 75025 233 75025 46368 1 28657 5 3 317811 987 8 233 24157817 21 2178309 8 21 55 39088169 3524578 610 17711 6765 987 5 832040 2 2 2178309 5 28657 13 39088169 1 14930352 514229 46368 17711 3 233 2584 377 832040 1 1346269 8 10946 610 377 377 2 13 17711 3 13 28657 17711 1597 102334155 610 21 102334155 10946 55 34 2 2178309 55 28657 102334155 9227465 63245986 5 165580141 1346269 144 2584 1597 1346269 21 5 102334155 13 2178309 55 2178309 317811 317811 17711 6765 34 34 28657 196418 144 39088169 9227465 377 3524578 3524578 233 4181 1597 1 8 4181 63245986 28657 2178309 28657 13 1 514229 102334155 34 3 46368 39088169 1346269 121393 4181 1597 75025 1 832040 10946 24157817 514229 121393 2178309 21 8 24157817 196418 4181 21 3524578 3524578 28657 2178309 121393 9227465 6765 39088169 28657 10946 987 2178309 144 3 987 39088169 165580141 39088169 63245986 2 3 10946 610 39088169 4181 3524578 2178309 63245986 165580141 8 832040 610 233 34 13 514229 14930352 121393 233 1346269 2584 5702887 2 102334155 5702887 1346269 2584 196418 4181 21 102334155 1 121393 317811 34 610 1346269 39088169 55 233 89 89 514229 832040 1 2 24157817 832040 39088169 317811 121393 832040 2178309 39088169 102334155 4181 14930352 832040 10946 10946 63245986 63245986 832040 165580141 514229 121393 987 196418 39088169 196418 377 1346269 1346269 4181 28657 3 21 10946 8 14930352 5 21 14930352 89 2584 317811 63245986 8 24157817 21 39088169 5 2584 1597 3 28657 4181 17711 2584 2584 21 832040 2178309 1597 24157817 46368 377 2 17711 13 5702887 2 514229 75025 144 63245986 2584 2 4181 2 89 987 2 196418 610 9227465 1346269 1 1 89 2178309 987 4181 17711 24157817 6765 987 1346269 987 5 46368 3 9227465 28657 63245986 102334155 8 9227465 21 832040 2178309 610 3 2584 14930352 1346269 1 39088169 21 377 196418 121393 610 46368 832040 832040 165580141 2178309 17711 8 1 144 3524578 3 24157817 2178309 10946 6765 1346269 3 9227465 14930352 89 28657 102334155 4181 2178309 4181 1 39088169 2 121393 21 377 46368 144 10946 55 46368 1 5702887 144 6765 6765 144 3 13 144 14930352 8 987 4181 1 21 3524578 55 10946 2178309 121393 514229 9227465 2584 317811 196418 9227465 17711 233 832040 75025 377 8 17711 196418 46368 3 2 6765 102334155 39088169 165580141 4181 9227465 610 317811 6765 8 196418 196418 8 514229 2 9227465 63245986 5 2 63245986 21 13 377 987 8 21 24157817 8 987 9227465 121393 610 233 28657 46368 832040 2584 514229 2178309 46368 2584 121393 1597 2 4181 13 165580141 17711 5702887 24157817 3524578 10946 34 377 39088169 144 832040 377 34 4181 196418 1597 21 1346269 17711 514229 5702887 24157817 987 2584 8 28657 14930352 1346269 987 2178309 46368 9227465 28657 514229 28657 377 17711 832040 2 9227465 832040 317811 13 14930352 317811 55 39088169 55 14930352 165580141 21 1 5 196418 75025 34 89 6765 55 3524578 63245986 63245986 2178309 121393 1 13 2584 8 4181 4181 28657 89 39088169 1 102334155 1597 63245986 8 144 987 55 2584 17711 610 377 24157817 34 196418 317811 121393 55 46368 28657 21 610 63245986 21 9227465 63245986 8 34 987 89 5702887 6765 2 46368 28657 121393 28657 987 2178309 4181 63245986 8 165580141 14930352 2 2 13 3 2 165580141 63245986 6765 1346269 39088169 24157817 9227465 165580141 165580141 233 39088169 832040 832040 8 39088169 55 6765 196418 1597 63245986 3524578 2 13 5702887 2 1346269 2178309 28657 34 89 63245986 2 17711 196418 377 9227465 2178309 3 514229 1 89 34 196418 1 39088169 6765 3 987 2178309 121393 1597 13 514229 14930352 610 102334155 17711 17711 13 2 4181 28657 1346269 102334155 89 987 6765 21 6765 102334155 610 102334155 102334155 10946 2178309 377 63245986 102334155 89 196418 63245986 21 9227465 13 610 377 46368 2584 2178309 165580141 63245986 75025 89 317811 102334155 144 39088169 63245986 2178309 514229 24157817 514229 121393 1 9227465 39088169 2 10946 3 46368 46368 28657 3524578 89 3 63245986 2584 75025 377 1 2 196418 39088169 3 1346269 17711 3524578 317811 2178309 1 832040 2178309 144 46368 5 6765 144 89 10946 39088169 63245986 4181 121393 17711 14930352 46368 17711 5702887 13 102334155 832040 10946 63245986 1 3524578 3 21 2178309 514229 39088169 24157817 3524578 121393 6765 317811 987 39088169 514229 514229 9227465 63245986 987 2 3524578 233 6765 514229 3524578 55 832040 14930352 3 6765 6765 1 3 3524578 2178309 2584 514229 28657 987 14930352 1 8 1 514229 121393 63245986 10946 2584 3 2584 2 1597 6765 102334155 832040 14930352 4181 1597 63245986 14930352 55 3 8 28657 5 89 233 63245986 21 1346269 3 196418 2584 1 5702887 377 13 14930352 14930352 17711 144 5 1 75025 987 3524578 21 1346269 17711 4181 21 610 34 21 14930352 121393 46368 514229 5 3524578 24157817 9227465 5 317811 8 233 377 5 63245986 102334155 75025 165580141 24157817 610 39088169 2 317811 377 317811 39088169 165580141 165580141 10946 3524578 34 233 89 28657 2584 102334155 9227465 1 63245986 13 1 233 17711 610 1597 17711 34 2178309 28657 55 2178309 13 317811 610 17711 4181 514229 514229 39088169 377 165580141 6765 1 2178309 55 144 28657 1346269 377 89 17711 14930352 1346269 1597 233 28657 63245986 9227465 317811 34 24157817 1346269 1346269 10946 514229 8 102334155 1597 610 1346269 10946 3 610 89 10946 24157817 196418 610 17711 21 514229 75025 165580141 89 17711 89 1346269 102334155 832040 2178309 89 2178309 5702887 8 196418 6765 377 39088169 1 233 377 34 4181 5 3524578 17711 233 987 24157817 9227465 75025 24157817 3 196418 34 1 13 196418 233 28657 233 5702887 2178309 233 89 3 55 13 610 10946 5 28657 6765 24157817 9227465 46368 987 832040 1346269 2 165580141 9227465 63245986 377