#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

unordered_map<int, int> mp;

void junkan2(int n)
{
    if(mp[n] > 0){ cout << mp[n] << '\n'; return; }
    int m = 1; // カメ。剰余を保持する変数（初期値1）
    int p = 1; // ウサギ。剰余を保持する変数（初期値1）
    int s = 0; // 循環節の開始位置
    int t = 0; // 循環節の終了位置
  
    if (n > 0)
    {
        // ウサギとカメが出合う地点を探す
        while (true)
        {
            m = (m * 10) % n;
            p = (p * 10) % n;
            p = (p * 10) % n;
            if (m == p)break;
        }
  
        // pが非ゼロ。割り切れない場合
        if (p != 0)
        {
            // ウサギをスタート地点に戻し、再びカメと出合うまでループを回す
            p = 1;
            s = 1;
            while (m != p)
            {
                s++;
                m = (m * 10) % n;
                p = (p * 10) % n;
            }
            // カメを止めて、ウサギだけ1ずつ進める
            p = (p * 10) % n;
            t = s;
            while (m != p)
            {
                t++;
                p = (p * 10) % n;
            }
        }
    }
    printf("%d\n", abs(s - t) + 1); // 結果を出力
    mp[n] = abs(s - t) + 1;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        junkan2(n);
    }
}