import math
import random

"""
p=19
q=37
n=p*q
phi=(p-1)*(q-1)
e=181
math.gcd(e, phi)==1
m=random.randint(1, n-1)
assert pow(m, e, n)==m
"""

def count_unconcealed_msg(e, n):
    unconcealed=0
    for m in range(1, n):
        if pow(m, e, n)==m:
            unconcealed=unconcealed+1
        #if unconcealed>8:
        #    return None
    return unconcealed

p=1009
q=3643
n=p*q
#print ("n", n)
phi=(p-1)*(q-1)
for e in range(1, phi):
    if math.gcd(e, phi)!=1:
        continue
    cnt=count_unconcealed_msg(e, n)
    #if cnt!=None and cnt<=8:
    #    print ("e", e, "cnt", cnt)
    print ("e", e, "cnt", cnt)