import java.util.*;
public class Main {
static int count=0;
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int i;
while(s.hasNextInt()) {
int tc=s.nextInt();
for(i=1;i<tc+1;i++) {
int n=s.nextInt();
classAssignment(n," ");
System.out.println("#"+i+" : "+count);
}
}
}
public static void classAssignment(int n,String result) {
if(result.length()==n)
{
count++;
return;
}
if(result.charAt(result.length()-1)=='b' && result.charAt(result.length()-2)=='b' ) {
return;
}
classAssignment(n,result+"a");
classAssignment(n,result+"b");
}
}