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 <typename TH>
void _dbg(const char* sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, t...);
}
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
template <class A, class B, class C>
struct Triple {
  A first;
  B second;
  C third;
  bool operator<(const Triple& t) const {
    if (first != t.first) return first < t.first;
    if (second != t.second) return second < t.second;
    return third < t.third;
  }
};
template <class T>
void ResizeVec(T&, vector<long long>) {}
template <class T>
void ResizeVec(vector<T>& vec, vector<long long> sz) {
  vec.resize(sz[0]);
  sz.erase(sz.begin());
  if (sz.empty()) {
    return;
  }
  for (T& v : vec) {
    ResizeVec(v, sz);
  }
}
template <class A, class B, class C>
ostream& operator<<(ostream& out, Triple<A, B, C> t) {
  return out << "(" << t.first << ", " << t.second << ", " << t.third << ")";
}
template <class T>
ostream& operator<<(ostream& out, vector<T> vec) {
  out << "(";
  for (auto& v : vec) out << v << ", ";
  return out << ")";
}
template <class T>
ostream& operator<<(ostream& out, set<T> vec) {
  out << "(";
  for (auto& v : vec) out << v << ", ";
  return out << ")";
}
long long mul(long long a, long long b, long long m) {
  long long r = 0;
  while (b) {
    if (b % 2) {
      r = (r + a) % m;
    }
    a = 2 * a % m;
    b /= 2;
  }
  return r;
}
long long spow(long long a, long long b, long long m) {
  long long r = 1;
  while (b) {
    if (b % 2) {
      r = mul(r, a, m);
    }
    a = mul(a, a, m);
    b /= 2;
  }
  return r;
}
struct Sol {
  void Test() {
    long long n;
    cin >> n;
    long long orig_n = n;
    long long pot10 = (long long)1e7;
    n *= pot10;
    long long pot2_18 = 1 << 18;
    for (long long milion = 0; milion < (10); ++milion) {
      long long rem = pot2_18 - (n % pot2_18);
      if (rem == pot2_18) {
        rem = 0;
      }
      if (rem % 10) {
        break;
      }
      ("was");
      n += (long long)1e6;
    }
    n = (n + pot2_18 - 1) / pot2_18 * pot2_18;
    (n);
    long long pot5_18 = 1;
    long long pot10_18 = 1;
    for (long long i = 0; i < (18); ++i) {
      pot5_18 *= 5;
      pot10_18 *= 10;
    }
    long long r = n % pot5_18;
    long long k = 0;
    if (r % 5 == 1) {
      k = 0;
    } else if (r % 5 == 2) {
      k = 1;
    } else if (r % 5 == 3) {
      k = 3;
    } else if (r % 5 == 4) {
      k = 2;
    } else {
      assert(false);
    }
    long long pot5_pom = 1;
    for (long long y = (1); y <= (17); ++y) {
      long long fi = pot5_pom * 4;
      long long to_mod = pot5_pom * 25;
      while (spow(2, k, to_mod) != r % to_mod) {
        k += fi;
      }
      pot5_pom *= 5;
    }
    k += pot5_pom * 20;
    (orig_n, spow(2, k, pot10_18));
    cout << k << "\n";
  }
};
int32_t main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  if (0) cout << fixed << setprecision(10);
  cin.tie(0);
  long long n;
  cin >> n;
  for (long long i = (1); i <= (n); ++i) {
    Sol sol;
    sol.Test();
  }
  return 0;
}