using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Globalization;
using System.Threading;
using static System.Math;
namespace FertiLib.Contest.E
{
public class Solver
{
Scanner sr;
StreamWriter sw;
bool isMultipleTestCases = true;
public void Solve()
{
var n = sr.ReadLong();
while (n % 2 == 0)
{
n /= 2;
}
while (n % 5 == 0)
{
n /= 5;
}
if (n == 1)
{
Console.WriteLine(1);
return;
}
var primes = Factorizer.Factorize(n);
var keta = n.ToString().Length;
long ans = 1;
foreach (var prime in primes)
{
for (int i = 0; i < prime.Value; i++)
{
ans *= prime.Key - 1;
}
}
var ansprimes = Factorizer.Factorize(ans);
foreach (var prime in ansprimes)
{
var c = prime.Value;
while (c > 0)
{
bool ok = true;
for (int i = 0; i < keta + 1; i++)
{
if (KthDigit(n, keta + i) != KthDigit(n, keta + i + ans / prime.Key))
{
ok = false;
break;
}
}
if (!ok) break;
{
ans /= prime.Key;
c--;
}
}
}
Console.WriteLine(ans);
}
public int KthDigit(long n, long k)
{
var p = Pow(10, k, 10 * n);
for (int i = 0; i < 10; i++)
{
if (i * n <= p && p < (i + 1) * n) return i;
}
throw new Exception();
}
public long Pow(long b, long pow, long mod)
{
BigInteger t = 1;
for (long i = 1; i <= pow; i <<= 1, b *= b, b %= mod)
{
if ((pow & i) > 0)
{
t *= b;
t %= mod;
}
}
return (long)t;
}
public Solver(Scanner cin, StreamWriter cout)
{
this.sr = cin;
this.sw = cout;
}
public void Start()
{
int _t = 1;
if (isMultipleTestCases) _t = sr.ReadInt();
while (_t-- > 0) Solve();
}
public static void YESNO(bool condition) => Console.WriteLine(condition ? "YES" : "NO");
public static void YesNo(bool condition) => Console.WriteLine(condition ? "Yes" : "No");
public static void yesno(bool condition) => Console.WriteLine(condition ? "yes" : "no");
}
public static class Factorizer
{
// http://miller-rabin.appspot.com/
static readonly long[] baseSingle = { 126401071349994536 }; // <= 291,831
static readonly long[] baseDouble = { 336781006125, 9639812373923155 }; // <= 1,050,535,501
static readonly long[] baseQuad = { 2, 2570940, 211991001, 3749873356 }; // <= 47,636,622,961,201
static readonly long[] baseBig = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
///
/// Factorizes n.
///
/// The number to factorize.
/// Dictionary that has prime factors in Key, the number of each factor in Value.
public static SortedDictionary Factorize(long n)
{
var ret = new SortedDictionary();
var que = new Queue();
que.Enqueue(n);
while (que.Count > 0)
{
var now = que.Dequeue();
if (now == 1) continue;
if (IsPrime(now))
{
if (ret.ContainsKey(now)) ret[now]++;
else ret.Add(now, 1);
continue;
}
long f = FindFactor(now);
que.Enqueue(f);
que.Enqueue(now / f);
}
return ret;
}
///
/// Tests if n is prime or not using Miller-Rabin Algorithm. Complexity: O(log^2 n)
///
/// The number to test.
/// True if prime, False otherwise.
public static bool IsPrime(long n)
{
if (n == 1) return false;
if (n == 2) return true;
long d = n - 1;
int s = 0;
while (d % 2 == 0)
{
d /= 2;
s++;
}
long[] bases;
if (n < 291831) bases = baseSingle;
else if (n < 1050535501) bases = baseDouble;
else if (n < 47636622961201) bases = baseQuad;
else bases = baseBig;
foreach (var e in bases)
{
if (!MillerRabinTest(e, d, n, s)) return false;
}
return true;
}
private static bool MillerRabinTest(long e, long d, long n, long s)
{
long pow = ModPow(e, d, n);
if (pow == 1) return true;
for (int i = 0; i < s; i++)
{
if (pow == n - 1) return true;
pow = ModPow(pow, 2, n);
}
return false;
}
private static long ModPow(long a, long p, long mod)
{
if (mod <= int.MaxValue)
{
a %= mod;
long ret = 1;
for (long i = 1; i <= p; i *= 2)
{
if (p / i % 2 == 1)
{
ret *= a;
ret %= mod;
}
a *= a;
a %= mod;
}
return ret;
}
else
{
BigInteger retbig = 1;
BigInteger abig = a % mod;
for (BigInteger i = 1; i <= p; i *= 2)
{
if (p / i % 2 == 1)
{
retbig *= abig;
retbig %= mod;
}
abig *= abig;
abig %= mod;
}
return (long)retbig;
}
}
///
/// Finds a factor of n by Pollard's ρ algorithm. Complexity: O(n^(1/4))
///
/// The number to get a factor.
/// A prime factor of n.
public static long FindFactor(long n)
{
if (n % 2 == 0) return 2;
long i = 0;
while (true)
{
i++;
long x = i;
long y = Next(i, n);
while (true)
{
long g = GCD(x - y, n);
if (g >= n) break;
if (1 < g) return g;
x = Next(x, n);
y = Next(y, n);
y = Next(y, n);
}
}
}
private static long Next(long x, long mod)
{
BigInteger tmp = x;
tmp *= tmp;
tmp++;
tmp %= mod;
return (long)tmp;
}
private static long GCD(long a, long b)
{
a = Math.Abs(a);
b = Math.Abs(b);
while (a > 0)
{
b %= a;
var x = a;
a = b;
b = x;
}
return b;
}
}
public static class Program
{
public static void Main(string[] args)
{
var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
var cin = new Scanner();
var solver = new Solver(cin, sw);
solver.Start();
Console.Out.Flush();
}
}
public static class Extention
{
public static string Join(this IEnumerable x, string separator = "") => string.Join(separator, x);
public static int UpperBound(this IList list, T value) => list.BinarySearch(value, true, 0, list.Count, Comparer.Default);
public static int LowerBound(this IList list, T value) => list.BinarySearch(value, false, 0, list.Count, Comparer.Default);
public static int BinarySearch(this IList list, T value, bool isUpperBound, int index, int length, Comparer comparer)
{
var ng = index - 1;
var ok = index + length;
while (ok - ng > 1)
{
var mid = ng + (ok - ng) / 2;
var res = comparer.Compare(list[mid], value);
if (res < 0 || (isUpperBound && res == 0)) ng = mid;
else ok = mid;
}
return ok;
}
public static bool Chmax(ref this T a, T b) where T : struct, IComparable
{
if (a.CompareTo(b) >= 0) return false;
a = b;
return true;
}
public static bool Chmin(ref this T a, T b) where T : struct, IComparable
{
if (a.CompareTo(b) <= 0) return false;
a = b;
return true;
}
}
public class Scanner
{
string[] s;
int i;
char[] separator = new char[] { ' ' };
public Scanner()
{
s = new string[0];
i = 0;
}
public string Read() => ReadString();
public string ReadString()
{
if (i < s.Length) return s[i++];
string st = Console.ReadLine();
while (st == "") st = Console.ReadLine();
s = st.Split(separator, StringSplitOptions.RemoveEmptyEntries);
if (s.Length == 0) return ReadString();
i = 0;
return s[i++];
}
public string[] ReadStringArray(int N)
{
string[] Array = new string[N];
for (int i = 0; i < N; i++)
{
Array[i] = ReadString();
}
return Array;
}
public int ReadInt() => int.Parse(ReadString());
public int[] ReadIntArray(int N, int add = 0)
{
int[] Array = new int[N];
for (int i = 0; i < N; i++)
{
Array[i] = ReadInt() + add;
}
return Array;
}
public long ReadLong() => long.Parse(ReadString());
public long[] ReadLongArray(int N, long add = 0)
{
long[] Array = new long[N];
for (int i = 0; i < N; i++)
{
Array[i] = ReadLong() + add;
}
return Array;
}
public double ReadDouble() => double.Parse(ReadString());
public double[] ReadDoubleArray(int N, double add = 0)
{
double[] Array = new double[N];
for (int i = 0; i < N; i++)
{
Array[i] = ReadDouble() + add;
}
return Array;
}
public T1 ReadValue() => (T1)Convert.ChangeType(ReadString(), typeof(T1));
public (T1, T2) ReadValue()
{
var inputs = ReadStringArray(2);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
return (v1, v2);
}
public (T1, T2, T3) ReadValue()
{
var inputs = ReadStringArray(3);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
return (v1, v2, v3);
}
public (T1, T2, T3, T4) ReadValue()
{
var inputs = ReadStringArray(4);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
return (v1, v2, v3, v4);
}
public (T1, T2, T3, T4, T5) ReadValue()
{
var inputs = ReadStringArray(5);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
return (v1, v2, v3, v4, v5);
}
public (T1, T2, T3, T4, T5, T6) ReadValue()
{
var inputs = ReadStringArray(6);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
return (v1, v2, v3, v4, v5, v6);
}
public (T1, T2, T3, T4, T5, T6, T7) ReadValue()
{
var inputs = ReadStringArray(7);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));
return (v1, v2, v3, v4, v5, v6, v7);
}
public T1[] ReadValueArray(int N)
{
var v1 = new T1[N];
for (int i = 0; i < N; i++)
{
v1[i] = ReadValue();
}
return v1;
}
public (T1[], T2[]) ReadValueArray(int N)
{
var (v1, v2) = (new T1[N], new T2[N]);
for (int i = 0; i < N; i++)
{
var (t1, t2) = ReadValue();
v1[i] = t1;
v2[i] = t2;
}
return (v1, v2);
}
public (T1[], T2[], T3[]) ReadValueArray(int N)
{
var (v1, v2, v3) = (new T1[N], new T2[N], new T3[N]);
for (int i = 0; i < N; i++)
{
var (t1, t2, t3) = ReadValue();
v1[i] = t1;
v2[i] = t2;
v3[i] = t3;
}
return (v1, v2, v3);
}
public (T1[], T2[], T3[], T4[]) ReadValueArray(int N)
{
var (v1, v2, v3, v4) = (new T1[N], new T2[N], new T3[N], new T4[N]);
for (int i = 0; i < N; i++)
{
var (t1, t2, t3, t4) = ReadValue();
v1[i] = t1;
v2[i] = t2;
v3[i] = t3;
v4[i] = t4;
}
return (v1, v2, v3, v4);
}
public (T1[], T2[], T3[], T4[], T5[]) ReadValueArray(int N)
{
var (v1, v2, v3, v4, v5) = (new T1[N], new T2[N], new T3[N], new T4[N], new T5[N]);
for (int i = 0; i < N; i++)
{
var (t1, t2, t3, t4, t5) = ReadValue();
v1[i] = t1;
v2[i] = t2;
v3[i] = t3;
v4[i] = t4;
v5[i] = t5;
}
return (v1, v2, v3, v4, v5);
}
public (T1[], T2[], T3[], T4[], T5[], T6[]) ReadValueArray(int N)
{
var (v1, v2, v3, v4, v5, v6) = (new T1[N], new T2[N], new T3[N], new T4[N], new T5[N], new T6[N]);
for (int i = 0; i < N; i++)
{
var (t1, t2, t3, t4, t5, t6) = ReadValue();
v1[i] = t1;
v2[i] = t2;
v3[i] = t3;
v4[i] = t4;
v5[i] = t5;
v6[i] = t6;
}
return (v1, v2, v3, v4, v5, v6);
}
public (T1[], T2[], T3[], T4[], T5[], T6[], T7[]) ReadValueArray(int N)
{
var (v1, v2, v3, v4, v5, v6, v7) = (new T1[N], new T2[N], new T3[N], new T4[N], new T5[N], new T6[N], new T7[N]);
for (int i = 0; i < N; i++)
{
var (t1, t2, t3, t4, t5, t6, t7) = ReadValue();
v1[i] = t1;
v2[i] = t2;
v3[i] = t3;
v4[i] = t4;
v5[i] = t5;
v6[i] = t6;
v7[i] = t7;
}
return (v1, v2, v3, v4, v5, v6, v7);
}
}
}