/** * author: shu8Cream * created: 15.01.2021 23:09:42 **/ #include using namespace std; #define rep(i,n) for (int i=0; i<(n); i++) #define all(x) (x).begin(), (x).end() using ll = long long; using P = pair; using vi = vector; using vvi = vector; void junkan(int n) { int m=1; // 剰余を保持する変数(初期値1) int s=0; // 循環節の開始位置 int t=0; // 循環節の終了位置 int*list=(int*)calloc(n-1,sizeof(int)); // リストの初期化 while (true) { // mが剰余リストにある場合はループ終了 for(s=0;list[s];s++) if(m==list[s]) goto END; // 剰余リストになかった場合は、終端に追加 list[s]=m; // 次の剰余を計算 m=(m*10)%n; // 割り切れる場合はループ終了 if(m==0)goto END; t++; } END: free(list); // リストの解放 if(t-s==0) cout << 1 << endl; else printf("%d\n", t-s); // 結果を出力 } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int t; cin >> t; while(t--){ int n; cin >>n; junkan(n); } }