//@formatter:off #include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define overload4(_1,_2,_3,_4,name,...) name #define rep1(i,n) for (ll i = 0; i < ll(n); ++i) #define rep2(i,s,n) for (ll i = ll(s); i < ll(n); ++i) #define rep3(i,s,n,d) for(ll i = ll(s); i < ll(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define rrep(i,n) for (ll i = ll(n)-1; i >= 0; i--) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back #define vi vector #define vvi vector> #define vl vector #define vvl vector> #define vd vector #define vvd vector> #define vs vector #define vc vector #define vvc vector> #define vb vector #define vvb vector> #define vp vector

#define vvp vector> #ifdef __LOCAL #define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; } #else #define debug(...) void(0) #endif #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) using namespace std; using ll = long long; using P = pair; using LP = pair; template istream& operator>>(istream &is,pair &p) { return is >> p.first >> p.second; } template ostream& operator<<(ostream &os,const pair &p) { return os<<'{'< istream& operator>>(istream &is,vector &v) { for(T &t:v){is>>t;} return is; } template ostream& operator<<(ostream &os,const vector &v) { os<<'[';rep(i,v.size())os< bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;} template bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;} void scan(){} template void scan(Head& head, Tail&... tail){ cin >> head; scan(tail...); } template void print(const T& t){ cout << t << '\n'; } template void print(const Head& head, const Tail&... tail){ cout< class prime { T n; public: prime(T n) : n(n) {} map factorlist() { if (n == 1) return {}; T nn = n; map ret; for (int i = 2; (ll) i * i <= n; i++) { if (nn % i != 0) continue; int cnt = 0; while (nn % i == 0) { cnt++; nn /= i; } ret[i] = cnt; } if (nn != 1) ret[nn]++; return ret; } vi unique_factor() { map m = factorlist(); vi ret; for (P p : m) ret.pb(p.first); return ret; }; bool isPrime() { auto v = factorlist(); return v.size() == 1 && v[0].second == 1; } int count_divisor() { int ret = 1; map fl = factorlist(n); for (auto p : fl) ret *= p.second + 1; return ret; }; vector enum_divisors() { vector res; for (T i = 1; i * i <= n; i++) { if (n % i == 0) { res.pb(i); if (n / i != i) res.pb(n / i); } } sort(all(res)); return res; } }; void solve() { INT(n); while (n % 2 == 0) n /= 2; while (n % 5 == 0) n /= 5; if (n == 1) { print(1); return; } ll now = 9; int y = 1; while (true) { if (now % n == 0) { print(y); return; } now *= 10; now += 9; now %= n; y++; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; rep(i, t) solve(); }