#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using K = long double;
ll a;
ull mul(ull a, ull b, ull mod) {
  ull q = (K)a * (K)b / (K)mod;
  ull rs = (a * b - q * mod + 5 * mod) % mod;
  return rs;
}
ll power(ll a, ll n, ll mod) {
  ll result = 1;
  while (n > 0) {
    if (n % 2) result = mul(result, a, mod);
    a = mul(a, a, mod);
    n /= 2;
  }
  return result;
}
void solve() {
  cin >> a;
  ll cur = 1;
  for (int pw = 0;; ++pw) {
    ll now = cur * a;
    ll b = (-now) & ((1LL << pw) - 1);
    if (now % (1LL << pw) == 0) {
      now += (1LL << pw);
    } else {
      now += b;
    }
    if (((int)(to_string(now)).size()) >= pw) continue;
    cur *= 10;
    if (now % 5 == 0) continue;
    if (to_string(now).find(to_string(a)) == string::npos) continue;
    now >>= pw;
    ll d = 0;
    while ((1LL << d) % 5 != now % 5) ++d;
    ll phi = 4;
    ll p5 = 5;
    for (int i = 1; i < pw; ++i) {
      ll here = 0;
      p5 *= 5;
      while (power(2, d + here * phi, p5) != now % p5) ++here;
      d += here * phi;
      phi *= 5;
    }
    cout << d + pw << '\n';
    return;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  for (int i = 0; i < (t); ++i) solve();
  return 0;
}
