N = int(input())
for query in range(N):
  p = int(input())
  for x in range(p*p):
    if pow(2,x,p) == x%p:
      print(x)
      break