#include <bits/stdc++.h>
using namespace std;

double find(double r) {
	double c = ceil(r);
	return r * c;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int k;
		scanf("%d", &k);
		double r = k + 0.5;
		int ans = 0;
		while (fmod(r, 1) != 0) {
			r = find(r);
			ans++;
			if (ans > 1000) {
				cout<<"NO!";
				break;
			}
		}
		if (fmod(r, 1) == 0) {
			cout<<ans;
		}
	}
	return 0;
}