#include<iostream>
using namespace std;

void count(char * in, int n, int i, char ch, int &c){
    if(i == n){
        in[i] = '\0';
        return;
    }
    if(i != 0 ){
         if( in[i-1] == in[i] && in[i-1] == 'b' && in[i] == 'b'){
            return;
            //why not this condition is being executed because of it recursion is not stopping at desired place
        }
    }


    in[i] = ch;
    if(i == n -1){
         c++;
          cout<<c<<endl;
          cout<<in<<" "<<i-1<<" "<<i<<endl;
    }

    count(in, n, i+1, 'a', c);
    count(in, n, i+1, 'b', c);
    in[i] = '\0';
    return;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        char *in = new char[n+1];
        int c = 0;
        count(in, n, 0, 'a', c);
      //  cout<<c<<endl;
        count(in, n, 0, 'b', c);
        cout<<c<<endl;

    }
    return 0;

}