Algorithm

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

MAIN113 - Special String

no tags 

 

A string of letters X, Y, Z is special if there are three consecutive letters from which one is X, one is Y, and one is Z. For example, XYZXYZ is special, while XXYYZ is not. Your task is to calculate how many such strings of length n are not special.

Input

First line contains an integer T (1 <= T <= 30) which denotes the total number of test cases. Each test case contains an integer N (1 <= N <= 30) in a single line.

Output

For each test case print total number of strings which have a length N and are not special.

Example

Input:
1
2

Output:
9

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

dp = [[0] * 9 for i in range(35)]
for i in range(3):
    dp[1][i] = 1
for i in range(9):
    dp[2][i] = 1
for i in range(3, 32):
    for j in range(9):
        (a, b) = (j / 3, j % 3)
        for k in range(3):
            if a != b and a != k and b != k:
                continue
            dp[i][a * 3 + k] += dp[i - 1][j]

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

Input

x
–
+
cmd
1
2

Output

x
–
+
cmd
9
Advertisements

Demonstration

SPOJ Solution-Special String-Solution in C, C++, Java, Python

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