public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		StringWriter out = new StringWriter();
		fillPre(LIM);
		while ((line = in.readLine()) != null && line.length() != 0) {
			int nSet = Integer.parseInt(line.trim());
			for (int i = 0; i < nSet; i++) {
				int k = Integer.parseInt(in.readLine());
				out.append(pre[k] + "\n");
			}
		}
		System.out.print(out);
	}