#include<bits/stdc++.h>
using namespace std;
int main() {
	long long n,k;
	double r;
	int t;
	cin >> t;
	while(t--) {
		cin>>k;
		r = k % 100 + 0.5;
		bool flag = 0;
		for (int i = 1; i <= 10000; i ++){
			r = r*(int)(r + 1);
			if ((int)r == r){
				flag = 1;
				cout << i << endl;
				break;
			}
			r = (int)r % 100 + 0.5;
		}
		if (flag == 0){
			cout << "NO!" << endl;
		}
	}
	return 0;
}

包互关的哈哈