Problem: You are given n positive integers a1, a2, ..., an.

For every ai you need to find a positive integer ki such that the decimal notation of 2ki contains the decimal notation of ai as a substring among its last min(100, length(2ki)) digits. Here length(m) is the length of the decimal notation of m.

Note that you don't have to minimize ki. The decimal notations in this problem do not contain leading zeros.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 000) — the number of integers ai.

Each of the next n lines contains a positive integer ai (1 ≤ ai < 1011).

Output

Print n lines. The i-th of them should contain a positive integer ki such that the last min(100, length(2ki)) digits of 2ki contain the decimal notation of ai as a substring. Integers ki must satisfy 1 ≤ ki ≤ 1050.

It can be shown that the answer always exists under the given constraints. If there are multiple answers, print any of them.

Examples

Input

2
8
2


Output

3
1


Input

2
3
4857


Output

5
20

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
long long mulmod(long long a, long long b, long long p) {
  a %= p, b %= p;
  long long q = (long long)((long double)a * b / p);
  long long r = a * b - q * p;
  while (r < 0) r += p;
  while (r >= p) r -= p;
  return r;
}
long long powmod(long long a, long long k, long long p) {
  if (!k) return 1;
  if (k & 1) return mulmod(powmod(a, k - 1, p), a, p);
  long long r = powmod(a, k >> 1, p);
  return mulmod(r, r, p);
}
long long findorder(int k) {
  if (!k) return 1;
  vector<long long> dvs;
  for (int a = 1; a <= 4; a <<= 1) {
    long long t = a;
    for (int i = (0); i < (k); ++i) {
      dvs.push_back(t);
      t *= 5;
    }
  }
  long long mod = powmod(5, k, LINF);
  sort((dvs).begin(), (dvs).end());
  for (long long x : dvs) {
    if (powmod(2, x, mod) == 1) {
      return x;
    }
  }
  assert(0);
  return -1;
}
long long solve(long long n, int k) {
  if (!k) return 0;
  long long r = solve(n, k - 1);
  long long mod = powmod(5, k, LINF);
  long long phi = findorder(k - 1);
  for (int i = (0); i < (5); ++i) {
    if (powmod(2, i * phi + r, mod) == n % mod) {
      return i * phi + r;
    }
  }
  assert(0);
  return -1;
}
int solve(long long n) {
  long long p2 = 1;
  long long p10 = 1;
  int t = 0;
  while (p10 <= n) {
    p2 *= 2;
    p10 *= 10;
    t++;
  }
  long long ptmp = p10;
  p10 = 1;
  while (t <= 18) {
    long long r = n % p2;
    long long nn = n + (p2 - r) % p2;
    if ((p2 - r) % p2 < p10 && nn % 5 != 0) {
      long long x = solve(nn, t) + findorder(t);
      assert(powmod(2, x, ptmp) == nn);
      cout << x << "\n";
      return 1;
    }
    p2 *= 2;
    ptmp *= 10;
    p10 *= 10;
    n *= 10;
    t++;
  }
  return 0;
}
void chemthan() {
  int test;
  cin >> test;
  while (test--) {
    long long n;
    cin >> n;
    if (!solve(n)) {
      for (int i = (1); i < (10); ++i) {
        if (solve(n * 10 + i)) {
          break;
        }
      }
    }
  }
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}