#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e9;
inline long long Mul(long long x, long long y, long long z) {
  long long t = 0;
  for (; y; y >>= 1, x = (x + x) % z)
    if (y & 1LL) t = (t + x) % z;
  return t;
}
inline long long mul(long long x, long long y, long long z) {
  return (x > inf || y > inf) ? Mul(x, y, z) : x * y % z;
}
inline long long Pow(long long x, long long y, long long z) {
  long long t = 1;
  for (; y; y >>= 1, x = mul(x, x, z))
    if (y & 1LL) t = mul(t, x, z);
  return t;
}
int main() {
  int i, j, _;
  for (cin >> _; _--;) {
    long long a;
    cin >> a;
    int A, B;
    long long t;
    for (A = 0, t = a; t; t /= 10) ++A;
    t = 1LL << (A + 1);
    long long t1 = 1;
    for (B = 0; t1 < t; ++B) t1 *= 10, t <<= 1;
    t1 *= a;
    t >>= 1;
    if (t1 % t) t1 += t - t1 % t;
    if (!(t1 % 5LL)) t1 += t;
    t1 /= t;
    long long x, y;
    for (t = 1, x = 0; t % 5LL != t1 % 5LL; t <<= 1, ++x)
      ;
    long long p = 4, q = 25;
    for (i = 2; i <= A + B; ++i) {
      t = Pow(2, x, q);
      y = Pow(2, p, q);
      for (; t != t1 % q; x += p) t = mul(t, y, q);
      p *= 5;
      q *= 5;
    }
    cout << x + A + B << endl;
  }
  return 0;
}
