#include <bits/stdc++.h>
using namespace std;
long long int scs(long long int a) {
  long long int u = 0;
  while (a) {
    u++;
    a /= 10;
  }
  return u;
}
long long int mul(long long int a, long long int b, long long int m) {
  long long int b1 = b / 1000000;
  long long int b2 = b % 1000000;
  return (((a * b1) % m * 1000000) % m + (a * b2) % m) % m;
}
long long int mu(long long int a, long long int n, long long int m) {
  if (n == 0) return 1 % m;
  long long int q = mu(a, n / 2, m);
  if (n % 2 == 0)
    return mul(q, q, m);
  else
    return mul(mul(q, q, m), a, m);
}
long long int mu5[20];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  mu5[0] = 1;
  for (int i = 1; i <= 19; i++) mu5[i] = mu5[i - 1] * 5;
  for (int z = 1; z <= t; z++) {
    long long int a;
    cin >> a;
    long long int n = scs(a);
    long long int v = 0, m = 0;
    for (int mmm = 0; mmm <= 6; mmm++) {
      m = mmm;
      long long int b = (-a) % (1LL << (m + n)) * mu5[m] % (1LL << (m + n)) *
                        (1LL << m) % (1LL << (m + n));
      b %= (1LL << (m + n));
      if (b < 0) b += (1LL << (m + n));
      bool q = 0;
      while (b < mu5[m] * (1LL << m)) {
        v = (b + mu5[m] * (1LL << m) * a) / (1LL << (m + n));
        if (v % 5 != 0) {
          q = 1;
          break;
        }
        b += (1LL << (m + n));
      }
      if (q == 1) {
        break;
      }
    }
    v %= mu5[m + n];
    long long int mm[4] = {1, 2, 4, 3};
    long long int res = 0;
    for (int i = 0; i <= 3; i++) {
      if (mm[i] == v % 5) res = i;
    }
    for (int i = 2; i <= m + n; i++) {
      long long int r = res;
      for (int u = 0; u <= 4; u++) {
        if (mu(2, r + u * 4 * mu5[i - 2], mu5[i]) == v % mu5[i]) {
          res = r + u * 4 * mu5[i - 2];
          break;
        }
      }
    }
    res += m + n;
    cout << res << endl;
  }
  return 0;
}
