Algorithm

Problem link- https://www.spoj.com/problems/NUMPLAY/

NUMPLAY - Fun with numbers

no tags 

 

Consider a set of 4 numbers {1, 3, 5, 7}. Form a number using these digits in the set under the following constraints,1 can be followed only by 3 (i.e. the number may contain 13 but not 15 or 17 or 11 eg:13573 is valid but not 113573), 3 can be followed only by 1 and 5, 5 can be followed only by 7, 7 can be followed only by 5 and 3.

Find the number of such numbers of length n.

e.g.: 37, 51, 53, 71 are all not a valid number of length 2. 131 is a valid number of length 3. 1357 and 1313 are all a valid number of length 4 but 11 or 1537 or 15 or 17 or 33 are not valid numbers.

Input

t, First line of input contains number of test cases 0 <= t <= 40.

Remaining t lines consist of length n for each test case 0 <= n <= 10000.

Output

Output the number of possible numbers of length n followed by a line (note long long int in C++ may not be sufficient.)

Example

Input:
3
2
1
4

Output:
6
4
13

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

dp = [[0 for i in range(4)] for j in range(10005)]

for i in range(4):
    dp[1][i] = 1
for i in range(2, 10004):
    dp[i][0] = dp[i - 1][1]
    dp[i][1] = dp[i - 1][0] + dp[i - 1][3]
    dp[i][2] = dp[i - 1][1] + dp[i - 1][3]
    dp[i][3] = dp[i - 1][2]

T = int(input())
for _ in range(T):
    N = int(input())
    print(sum(dp[N]))
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
2
1
4

Output

x
–
+
cmd
6
4
13
Advertisements

Demonstration

SPOJ Solution-Fun with numbers-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python