#include
using namespace std;
void helper(int n,char* output,int j,int &count){
//base case
if(j>=n){
output[j]=’\0’;
count++;
return;
}
//recursive case
//all a’s will be printed
output[j]=‘a’;
helper(n,output,j+1,count);
//all b’s will be printed;
if(output[j-1]!=‘b’){
output[j]=‘b’;
helper(n,output,j+1,count);
}
}
int main() {
int test;
cin>>test;
int i=0;
while(i<test){
int n;
cin>>n;
char output[100];
int count=0;
helper(n,output,0,count);
cout<<"#"<<n<<" “<<”:"<<" "<<count<<endl;
i++;
}
}