# 2912.py

# Test di Lucas-Lehmer per numeri di Mersenne 2^p-1.
def lucas (p):
  if p==2: return 1
  n=pow(2,p)-1; A=4%n
  for k in range(2,p): A=(A*A-2)%n
  if A%n: return 0
  return 1

for p in [2,3,5,7,11,13,17,19,23]: print (p,lucas(p))