import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    private static int cycleLength(int x) {
        if(x == 0) {
            return 0;
        }
        int NotSeenYet = 0;
        int[] lastPos = new int[x];
        int position = 1;
        int dividend = 1;
        while(true) {
            int remainder = dividend % x;
            if(remainder == 0) {
                return 0;
            }
            if(lastPos[remainder] != NotSeenYet) {
                return position - lastPos[remainder];
            }
            lastPos[remainder] = position;
            position++;
            dividend = remainder * 10;
        }
    }

    public static void main(String[] args) {
        int MaxD = 10000;
        int[] cache = new int[MaxD + 1];
        int longD = 0;
        int longC = 0;
        for(int D = 1; D <= MaxD; D++) {
            int length = cycleLength(D);
            if(longC < length) {
                longC = length;
                longD = D;
            }
            cache[D] = longD;
        }
        System.out.println(Arrays.toString(cache));
        try(Scanner sc = new Scanner(System.in)) {
            int T = sc.nextInt();
            while(T-- > 0) {
                int N = sc.nextInt();
                System.out.println(cache[N - 1]);
            }
        }
    }
}