#include <bits/stdc++.h>
using namespace std;
const int N = 20;
long long p2[N], p5[N], p10[N];
long long dp[N];
void init() {
  int i;
  p2[0] = p5[0] = p10[0] = 1;
  for (i = 1; i <= 18; i++) p2[i] = p2[i - 1] * 2;
  for (i = 1; i <= 18; i++) p5[i] = p5[i - 1] * 5;
  for (i = 1; i <= 18; i++) p10[i] = p10[i - 1] * 10;
}
long long phi(int n) { return p5[n] - p5[n - 1]; }
long long mul(long long x, long long y, long long mod) {
  if (mod <= p10[9]) return x * y % mod;
  long long ret = 0;
  for (; y; y >>= 1, x = (x + x) % mod) {
    if (y & 1) ret = (ret + x) % mod;
  }
  return ret;
}
long long power(long long x, long long y, long long mod) {
  long long ret = 1;
  for (; y; y >>= 1, x = mul(x, x, mod)) {
    if (y & 1) ret = mul(ret, x, mod);
  }
  return ret;
}
long long Log(long long y, int n) {
  int i, j;
  for (i = 0; i <= 4; i++)
    if (power(2, i, 5) == y % 5) dp[1] = i;
  for (i = 2; i <= n; i++)
    for (j = 0; j <= 4; j++)
      if (power(2, dp[i - 1] + j * phi(i - 1), p5[i]) == y % p5[i]) {
        dp[i] = (dp[i - 1] + j * phi(i - 1)) % phi(i);
        break;
      }
  return dp[n];
}
int main() {
  int T;
  long long a, b, ans, x, y;
  int n, m;
  init();
  scanf("%d", &T);
  while (T--) {
    scanf("%I64d", &a);
    for (b = a, n = 0; b; n++, b /= 10)
      ;
    for (m = 0; p10[m] <= p2[n + m + 1]; m++)
      ;
    for (x = p2[n + m] - p10[m] * a % p2[n + m]; x % 5 == 0; x += p2[n + m])
      ;
    x += p10[m] * a;
    y = x / p2[n + m];
    ans = Log(y, n + m) + n + m;
    printf("%I64d\n", ans);
  }
}
