#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int t; cin >> t; for (int i = 0; i < t; i++) { long long n; cin >> n; while (n % 2 == 0) { n /= 2; } while (n % 5 == 0) { n /= 5; } long long k = 9; for (int j = 1;; j++) { k %= n; if (k == 0) { cout << j << endl; break; } k *= 10; k += 9; } } }