/*
 * ISPC 2006 / Gotta pick'em all - Easy solution
 * Coded by Goober
 */
  
#include <stdio.h>

int main() {
  int precal[10] = { 0, 1, 1, 3, 2, 6, 1, 6, 1, 5 };
  int n;
  scanf("%*d");
  while(scanf("%d", &n) == 1) printf("%d\n", (n<10) ? precal[n] : (n&1) ? 4 : 1);
  return 0;
}