#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() 
{
    int T, N, count;
    vector<int> vec;
 
    cin >> T;
 
    while(T--)
    {
        cin >> N;
 
        vec.clear();
        count = 0;
 
        do
        {
            vec.push_back(N);
            N = (N * N / 100) % 10000;
 
            count++;
        }
        while(find(vec.begin(), vec.end(), N) == vec.end());
 
        cout << count << " ";
    }
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSAKewogICAgaW50IFQsIE4sIGNvdW50OwogICAgdmVjdG9yPGludD4gdmVjOwogICAgCiAgICBjaW4gPj4gVDsKICAgIAogICAgd2hpbGUoVC0tKQogICAgewogICAgICAgIGNpbiA+PiBOOwogICAgICAgIAogICAgICAgIHZlYy5jbGVhcigpOwogICAgICAgIGNvdW50ID0gMDsKICAgICAgICAKICAgICAgICBkbwogICAgICAgIHsKICAgICAgICAgICAgdmVjLnB1c2hfYmFjayhOKTsKICAgICAgICAgICAgTiA9IChOICogTiAvIDEwMCkgJSAxMDAwMDsKICAgICAgICAgICAgCiAgICAgICAgICAgIGNvdW50Kys7CiAgICAgICAgfQogICAgICAgIHdoaWxlKGZpbmQodmVjLmJlZ2luKCksIHZlYy5lbmQoKSwgTikgPT0gdmVjLmVuZCgpKTsKICAgICAgICAKICAgICAgICBjb3V0IDw8IGNvdW50IDw8ICIgIjsKICAgIH0KICAgICAgICAKICAgIHJldHVybiAwOwp9

MTQKNTU5OSA3NTYxIDEwMjIgNTgxMCA4ODQ4IDE2ODcgNDU4NyAzMTg1IDMwMjggNzgxNyA4MjA2IDYyMTIgOTY5MiA1Njkw

14
5599 7561 1022 5810 8848 1687 4587 3185 3028 7817 8206 6212 9692 5690