import java.util.*;
public class Main {
public static int func(int n, String str){
if(n == 0)
return 1;
int count = 0;
count += func(n-1,str+"b");
if(str.length() == 0 || str.charAt(str.length()-1) == 'b')
count += func(n-1,str+"a");
return count;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i = 0; i < t; i++){
int n = sc.nextInt();
System.out.println("#" + n + " : " + func(n,""));
}
}
}