#include <cstdio>
#include <algorithm>
#define oo 987654321

int dt3[130], dt4[130], dt5[130], cnt[130];

using namespace std;

long long int h3(int n)
{
    if( n == 1 ) return 1;
    if( n > 20 ) return oo;
    if( dt3[n] ) return dt3[n];
    return dt3[n] = h3(n-1) + 1 + h3(n-1);
}

long long int h4(int n)
{
    if( n == 1 ) return 1;
    if( dt4[n] ) return dt4[n];
    long long int ret = oo;
    for(int i = 1 ; i < n ; i++ )
        if( ret > h4(i) + h3(n-i) + h4(i) )
            ret = h4(i) + h3(n-i) + h4(i), cnt[n] = i;
    return dt4[n] = ret;
}

void hanoi3(int n, char a, char b, char c, int inc)
{
    if( n > 0 )
    {
        hanoi3(n-1, a, c, b, inc);
        printf("%d : %c->%c\n", n+inc, a, c);
        hanoi3(n-1, b, a, c, inc);
    }
}

void hanoi4(int n, char a, char b, char c, char d)
{
    if( n > 0 )
    {
        hanoi4(cnt[n], a, c, d, b);
        hanoi3(n-cnt[n], a, c, d, cnt[n]);
        hanoi4(cnt[n], b, a, c, d);
    }
}

int main()
{
    freopen(".10.in","r",stdin);
    freopen(".10.out","w",stdout);
    int n;
    scanf("%d", &n);
    printf("%d\n", h4(n));
    hanoi4(n, 'A', 'B', 'C', 'D');
}