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;
template <class T>
inline void gmin(T &x, const T &y) {
  x = x > y ? y : x;
}
template <class T>
inline void gmax(T &x, const T &y) {
  x = x < y ? y : x;
}
template <class T>
inline bool Gmin(T &x, const T &y) {
  return x > y ? x = y, 1 : 0;
}
template <class T>
inline bool Gmax(T &x, const T &y) {
  return x < y ? x = y, 1 : 0;
}
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Bufferhead, *Buffertail;
bool Terminal;
inline char Getchar() {
  if (Bufferhead == Buffertail) {
    int l = fread(buffer, 1, BufferSize, stdin);
    if (!l) {
      Terminal = 1;
      return 0;
    }
    Buffertail = (Bufferhead = buffer) + l;
  }
  return *Bufferhead++;
}
template <class T>
inline bool read(T &x) {
  x = 0;
  char c = Getchar(), rev = 0;
  while (c < '0' || c > '9') {
    rev |= c == '-';
    c = Getchar();
    if (Terminal) return 0;
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = Getchar();
  if (c == '.') {
    c = Getchar();
    double t = 0.1;
    while (c >= '0' && c <= '9')
      x = x + (c - '0') * t, c = Getchar(), t = t / 10;
  }
  x = rev ? -x : x;
  return 1;
}
template <class T1, class T2>
inline bool read(T1 &x, T2 &y) {
  return read(x) & read(y);
}
template <class T1, class T2, class T3>
inline bool read(T1 &x, T2 &y, T3 &z) {
  return read(x) & read(y) & read(z);
}
template <class T1, class T2, class T3, class T4>
inline bool read(T1 &x, T2 &y, T3 &z, T4 &w) {
  return read(x) & read(y) & read(z) & read(w);
}
inline bool reads(char *x) {
  char c = Getchar();
  while (c < 33 || c > 126) {
    c = Getchar();
    if (Terminal) return 0;
  }
  while (c >= 33 && c <= 126) (*x++) = c, c = Getchar();
  *x = 0;
  return 1;
}
template <class T>
inline void print(T x, const char c = '\n') {
  if (!x) {
    putchar('0');
    putchar(c);
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  int m = 0, a[20];
  while (x) a[m++] = x % 10, x /= 10;
  while (m--) putchar(a[m] + '0');
  putchar(c);
}
const int inf = 0x3f3f3f3f;
const int N = 200005, M = 100005, mod = 1e9 + 7;
template <class T, class S>
inline void ch(T &x, const S y) {
  x = (x + y) % mod;
}
inline long long mul(long long x, long long y, long long mod) {
  long long t = x * y - (long long)((long double)x * y / mod) * mod;
  return t < 0 ? t + mod : t;
}
inline long long exp(long long x, long long y, long long mod) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = mul(ans, x, mod);
    x = mul(x, x, mod);
    y >>= 1;
  }
  return ans;
}
inline int getlen(long long a) {
  int ans = 0;
  while (a) a /= 10, ans++;
  return ans;
}
inline long long calc(int g, int p, int a, long long x) {
  long long mod = p, phi = p - 1, d = 0;
  for (int i = 0, pw = 1; i < p; i++) {
    if (pw == x % p) {
      d = i;
      break;
    }
    pw = (long long)pw * g % p;
  }
  for (int i = 2; i <= a; i++) {
    mod *= p;
    for (;; d += phi)
      if (exp(g, d, mod) == x % mod) break;
    phi *= p;
  }
  return d;
}
int Main(int argv) {
  long long a;
  read(a);
  int n;
  n = getlen(a);
  for (int m = 0;; m++) {
    long long b = (-a) & ((1ll << n + m) - 1);
    cerr << "m"
         << "=" << m << endl;
    if (m && b % 5 == 0) b += (1ll << n + m);
    if (!m && a % 5 == 0) goto power;
    if (getlen(b) <= m) {
      print(calc(2, 5, n + m, (a + b) >> n + m) + n + m);
      return 0;
    }
  power:
    a *= 10;
  }
  return 0;
}
void clear() {}
int main() {
  int T;
  scanf("%d", &T);
  for (int i = 1; i <= T; i++) Main(i), clear();
  return 0;
}