#include <stdio.h>
#include <string.h>
 
void swap( char* a, char* b )
{
	char t = *a;
	*a = *b;
	*b = t;
}
 
void reverse( char* str, int low, int high )
{
	while( low < high )
	{
		swap( &str[low], &str[high] );
		++low;
		--high;
	}
}
 
void cycleLeaderIteration( char* str, int shift, int len )
{
	int i, j, item, element;
 
	for( i = 1; i < len; i *= 3 )
	{
		j = i;
 
		item = str[j + shift];
		do
		{
			// odd index
			if( j & 1 )
				j = len / 2 + j / 2;
			// even index
			else
				j /= 2;
 
			// keep the back-up of element at new position
			element = str[j + shift];
 
			str[j + shift] = item;
 
			item = element;
		} while( j != i );
	}
}
 
void moveNumberToSecondHalf( char* str )
{
	int i, j, k, lenFirst, lenRemaining, shift;
 
	lenRemaining = strlen( str );
	shift = 0;
 
	while( lenRemaining )
	{
		k = 0;
		while( pow( 3, k ) + 1 <= lenRemaining )
			k++;
 
		lenFirst = pow( 3, k - 1 ) + 1;
		lenRemaining -= lenFirst;
 
		cycleLeaderIteration( str, shift, lenFirst );
 
 
		reverse( str, shift / 2, shift - 1 );
 
		reverse( str, shift, shift + lenFirst / 2 - 1 );
 
		reverse( str, shift / 2, shift + lenFirst / 2 - 1 );
 
		shift += lenFirst;
	}
}
 
void Test()
{
	int len, i, alph, digit ;
	char str[100];
 
	for( len = 2; len <= 52; len += 2 )
	{
		for( i = 0; i < len; i++ )
		{
			if( i & 1 )
				str[i] = i / 2 % 9 + 1 + '0';
			else
				str[i] = i / 2 + 'a';
		}
		str[ len ] = '\0';
 
		printf( "Test case#%d\n", len / 2 );
		printf( "%s\n", str );
 
		moveNumberToSecondHalf( str );
 
		printf( "%s\n\n\n", str );
	}
}
 
int main()
{
	Test();
 
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KCnZvaWQgc3dhcCggY2hhciogYSwgY2hhciogYiApCnsKCWNoYXIgdCA9ICphOwoJKmEgPSAqYjsKCSpiID0gdDsKfQoKdm9pZCByZXZlcnNlKCBjaGFyKiBzdHIsIGludCBsb3csIGludCBoaWdoICkKewoJd2hpbGUoIGxvdyA8IGhpZ2ggKQoJewoJCXN3YXAoICZzdHJbbG93XSwgJnN0cltoaWdoXSApOwoJCSsrbG93OwoJCS0taGlnaDsKCX0KfQoKdm9pZCBjeWNsZUxlYWRlckl0ZXJhdGlvbiggY2hhciogc3RyLCBpbnQgc2hpZnQsIGludCBsZW4gKQp7CglpbnQgaSwgaiwgaXRlbSwgZWxlbWVudDsKCglmb3IoIGkgPSAxOyBpIDwgbGVuOyBpICo9IDMgKQoJewoJCWogPSBpOwoKCQlpdGVtID0gc3RyW2ogKyBzaGlmdF07CgkJZG8KCQl7CgkJCS8vIG9kZCBpbmRleAoJCQlpZiggaiAmIDEgKQoJCQkJaiA9IGxlbiAvIDIgKyBqIC8gMjsKCQkJLy8gZXZlbiBpbmRleAoJCQllbHNlCgkJCQlqIC89IDI7CgkKCQkJLy8ga2VlcCB0aGUgYmFjay11cCBvZiBlbGVtZW50IGF0IG5ldyBwb3NpdGlvbgoJCQllbGVtZW50ID0gc3RyW2ogKyBzaGlmdF07CgkJCgkJCXN0cltqICsgc2hpZnRdID0gaXRlbTsKCgkJCWl0ZW0gPSBlbGVtZW50OwoJCX0gd2hpbGUoIGogIT0gaSApOwoJfQp9Cgp2b2lkIG1vdmVOdW1iZXJUb1NlY29uZEhhbGYoIGNoYXIqIHN0ciApCnsKCWludCBpLCBqLCBrLCBsZW5GaXJzdCwgbGVuUmVtYWluaW5nLCBzaGlmdDsKCglsZW5SZW1haW5pbmcgPSBzdHJsZW4oIHN0ciApOwoJc2hpZnQgPSAwOwoKCXdoaWxlKCBsZW5SZW1haW5pbmcgKQoJewoJCWsgPSAwOwoJCXdoaWxlKCBwb3coIDMsIGsgKSArIDEgPD0gbGVuUmVtYWluaW5nICkKCQkJaysrOwoKCQlsZW5GaXJzdCA9IHBvdyggMywgayAtIDEgKSArIDE7CgkJbGVuUmVtYWluaW5nIC09IGxlbkZpcnN0OwoKCQljeWNsZUxlYWRlckl0ZXJhdGlvbiggc3RyLCBzaGlmdCwgbGVuRmlyc3QgKTsKCgoJCXJldmVyc2UoIHN0ciwgc2hpZnQgLyAyLCBzaGlmdCAtIDEgKTsKCgkJcmV2ZXJzZSggc3RyLCBzaGlmdCwgc2hpZnQgKyBsZW5GaXJzdCAvIDIgLSAxICk7CgoJCXJldmVyc2UoIHN0ciwgc2hpZnQgLyAyLCBzaGlmdCArIGxlbkZpcnN0IC8gMiAtIDEgKTsKCgkJc2hpZnQgKz0gbGVuRmlyc3Q7Cgl9Cn0KCnZvaWQgVGVzdCgpCnsKCWludCBsZW4sIGksIGFscGgsIGRpZ2l0IDsKCWNoYXIgc3RyWzEwMF07CgoJZm9yKCBsZW4gPSAyOyBsZW4gPD0gNTI7IGxlbiArPSAyICkKCXsKCQlmb3IoIGkgPSAwOyBpIDwgbGVuOyBpKysgKQoJCXsKCQkJaWYoIGkgJiAxICkKCQkJCXN0cltpXSA9IGkgLyAyICUgOSArIDEgKyAnMCc7CgkJCWVsc2UKCQkJCXN0cltpXSA9IGkgLyAyICsgJ2EnOwoJCX0KCQlzdHJbIGxlbiBdID0gJ1wwJzsKCgkJcHJpbnRmKCAiVGVzdCBjYXNlIyVkXG4iLCBsZW4gLyAyICk7CgkJcHJpbnRmKCAiJXNcbiIsIHN0ciApOwoKCQltb3ZlTnVtYmVyVG9TZWNvbmRIYWxmKCBzdHIgKTsKCgkJcHJpbnRmKCAiJXNcblxuXG4iLCBzdHIgKTsKCX0KfQoKaW50IG1haW4oKQp7CglUZXN0KCk7CgoJcmV0dXJuIDA7Cn0=