#include <iostream>
#include <string>
#include <set>
using namespace std;
void perm(int n, int i, string output, set<string> &s){
if (i == n){
string temp(output);
s.insert(temp);
return;
}
perm(n, i + 1, output + "a", s);
if (output[i - 1] == 'b'){
perm(n, i + 1, output + "a", s);
} else {
perm(n, i + 1, output + "b", s);
}
return;
}
int main(){
int t;
cin >> t;
int i = 1;
while (t--){
int n, count = 0;
cin >> n;
set<string> s;
perm(n, 0, "", s);
// cout << s.size() << endl;
cout << "#" << i << " : " << s.size() << endl;
i++;
}
}
