public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int arr[] = new int[10001];
		for (int i = 1; i * i <= 10000; i++)
			arr[i * i] = 1;
		for (int cont = 1; cont < 4; cont++) 
			for (int i = 1; i <= 10000; i++) 
				if (arr[i] == 1)
					for (int j = 1; j <= 10000; j++) 
						if (arr[j] == cont && i + j <= 10000)
							if (arr[i + j] == 0)
								arr[i + j] = 1 + arr[j];
		for (int i = 0, n = Integer.parseInt(in.readLine().trim()); i < n; i++) {
			int x = Integer.parseInt(in.readLine().trim());
			System.out.println(arr[x]);
		}
	}