ll a[1000];
int b[1000];
{
	ll@t;
	rep(t){
		ll@n;
		while(n%2==0) n/=2;
		while(n%5==0) n/=5;
		if(n==1) wt(1),continue;
		ll a=1,b=n;
		modint x;
		x.setmod(n);
		while(a+1<b){
			ll c=a+b>>1;
			x=10;
			x**=(n-1)/c;
			if(x==1){
				a=c;
			}else{
				b=c;
			}
		}
		wt((n-1)/a);
	}
}