// c# using System;

public class Program { static int FindCycle(int n) { int[] seen = new int[n]; seen[1] = 1; int m = 1; int i = 2;

    while (true)
    {
        m *= 10;
        int p = m % n;
        if (p == 0)
            return 0;
        if (seen[p] != 0)
            return i - seen[p];
        seen[p] = i;
        i++;
        m = p;
    }
}

public static void Main(string[] args)
{
    int[] ans = new int[10001];
    int[] cycleLength = new int[10001];
    ans[2] = 3;
    cycleLength[2] = 1;
    ans[3] = 3;
    cycleLength[3] = 1;

    for (int i = 4; i <= 10000; i++)
    {
        int p = FindCycle(i);
        if (p > cycleLength[ans[i - 1]])
        {
            ans[i] = i;
            cycleLength[i] = p;
        }
        else
        {
            ans[i] = ans[i - 1];
            cycleLength[i] = cycleLength[i - 1];
        }
    }

    int t = int.Parse(Console.ReadLine());
    for (int _ = 0; _ < t; _++)
    {
        int n = int.Parse(Console.ReadLine());
        Console.WriteLine(ans[n - 1]);
    }
}

}