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;
long long pwr(long long x, int y) {
  long long p = 1;
  while (y--) {
    p *= x;
  }
  return p;
}
long long add(long long x, long long y, long long md) {
  x = (x + y) % md;
  if (x < 0) {
    x += md;
  }
  return x;
}
void addeq(long long &x, long long y, long long md) { x = add(x, y, md); }
long long subtr(long long x, long long y, long long md) {
  x = (x - y) % md;
  if (x < 0) {
    x += md;
  }
  return x;
}
long long mult(long long x, long long y, long long md) {
  const static int BLOCK = 1e6;
  long long yl = y / BLOCK, yr = y % BLOCK;
  return add(yr * x % md, yl * x % md * BLOCK % md, md);
}
void multeq(long long &x, long long y, long long md) { x = mult(x, y, md); }
long long pwr(long long x, long long y, long long md) {
  long long res = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      multeq(res, x, md);
    }
    multeq(x, x, md);
  }
  return res;
}
long long pwr5[20];
void precomp() {
  pwr5[0] = 1;
  for (int i = 1; i < 20; i++) {
    pwr5[i] = pwr5[i - 1] * 5;
  }
}
long long A;
int N, M;
long long go() {
  N = to_string(A).size();
  M = 17 - N;
  int opwr = 1 << 17;
  long long fro = pwr(10, M) * A;
  ;
  long long rem = fro + subtr(0, fro, opwr);
  if (rem % 5 == 0) {
    rem += opwr;
  };
  rem %= pwr5[17];
  ;
  long long curv = rem;
  long long curb = (pwr5[17] + 1) / 2;
  long long modp516 = 0;
  for (int i = 2; i <= 17; i++) {
    ;
    for (int j = 0; j < 5; j++) {
      ;
      if (pwr(curv % pwr5[i], 4, pwr5[i]) == 1) {
        break;
      }
      multeq(curv, curb, pwr5[17]);
      modp516 += pwr5[i - 2];
    };
    curb = pwr(curb, 5, pwr5[17]);
    ;
  };
  int mod4;
  if (rem % 5 == 1) {
    mod4 = 0;
  } else if (rem % 5 == 2) {
    mod4 = 1;
  } else if (rem % 5 == 4) {
    mod4 = 2;
  } else if (rem % 5 == 3) {
    mod4 = 3;
  } else {
    assert(!"Divisible by 5!?");
  }
  long long res = modp516;
  while (res < 100 || res % 4 != mod4) {
    res += pwr5[16];
  }
  return res;
}
int main() {
  precomp();
  int nq;
  scanf("%d", &nq);
  for (int qi = 0; qi < nq; qi++) {
    scanf("%lld", &A);
    printf("%lld\n", go());
  }
}