import math
import random

def count_unconcealed_msg(mega_array, n):
    unconcealed=0
    for i in range(1, len(mega_array)-1):
        assert mega_array[i]<n
        if mega_array[i]==i:
            unconcealed=unconcealed+1
    return unconcealed

p=1009
q=3643
n=p*q
phi=(p-1)*(q-1)
print ("n, phi", n, phi)
mega_array=[0]+[i for i in range(1, n+1)]

for e in range(1, phi):
    if math.gcd(e, phi)==1:
        cnt=count_unconcealed_msg(mega_array, n)
        print ("e", e, "cnt", cnt)
    # mul each element by m
    for i in range(1, n-1):
        mega_array[i]=divmod(mega_array[i]*i, n)[1]