Class Assignment

 In a mathematics class, Teacher ask Alice to find the number of all n digit distinct integers which is formed by the two distinct digits ai and bi but there is a rule to form n digit integer.

Rule: She has to form n digit integer by using two digits ai and bi without consecutive bi.

Alice is very weak in maths section. Help her to find the number of such n digit integers.

Input Format

The first line contains T, the number of test cases. Further T lines contains the value n which is the number of digit in the integer.

Constraints

1<=T<=20
1<=n<=25

Output Format

For each test case print the number of such n digit integer.

Sample Input

3
1
2
3

Sample Output

#1 : 2
#2 : 3
#3 : 5

Explanation

For n=1 : integers = a, b . 

For n=2 : integers = aa, ab, ba

For n=3 : integers = aaa, aab, aba, baa, bab

import java.util.Scanner;

public class ClassAssignmentProblem
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
int length=s.nextInt();
int arr[]=new int[length];
for(int i=0; i<arr.length; i++)
{
arr[i]=s.nextInt();
}
for(int i=0; i<arr.length; i++)
{
int result=classAssignmentProblemSolution(arr[i],"");
System.out.println("#"+(i+1)+" "+":"+" "+result);

}
s.close();
}
public static int classAssignmentProblemSolution(int num,String ans)
{
if(ans.length()==num)
{
return 1;
}
if(ans.length()>=num)
{
return 0;
}
int count=0;
count+=classAssignmentProblemSolution(num, ans+"a");
if(ans.length()==0 || ans.charAt(ans.length()-1)!='b')
{
count+=classAssignmentProblemSolution(num, ans+"b");
}
return count;
}

}