#include <stdio.h>
#include <math.h>

double a;
unsigned int N;

int main (){
	short i;
	
	while ( scanf ( "%d", &N ) ){
		if (!N) break;
		
		for (i=31, a=0; i>=1; i--){
			a=pow ( N, (double)1/i );
			if ((int)a && fabs ( a-(int)a )<=0.0000001) break;
		}
		printf ( "%d\n", i );
	}
	
	return 0;
}