#!/usr/bin/env python -i

from fractions import gcd

def Jacobi(m, n):
	if (n % 2) == 0:
		raise Exception("n cannot be even")
	if (m == 1):
		return 1
	elif (m == 2) and (n > 0) and (n % 2 == 1):
		a = n % 8
		if (a == 1) or (a == 7):
			return 1
		elif (a == 3) or (a == 5):
			return -1
	elif m % n == 0:
		return 0
	elif (m >= n) or (m < 0):
		#print('(%d/%d)' % (m%n, n))
		return Jacobi(m % n, n)
	elif m % 2 == 0:
		#print('(%d/%d)*(2/%d)' % (m/2, n, n))
		return Jacobi(m / 2, n) * Jacobi(2, n)
	elif (m % 2 == 1) and (n % 2 == 1):
		if (m % 4 == 3) and (n % 4 == 3):
			#print('-(%d/%d)' % (n, m))
			return -Jacobi(n, m)
		else: 
			#print('(%d/%d)' % (n, m))
			return Jacobi(n, m)
			
def NumberOfPseudoPrimes(n):
	# We'll just list'em all, and then count.
	i = 0
	for a in range(0, n):
		if gcd(a, n) == 1:
			if (Jacobi(a, n) % n) == (a**((n-1)/2)) % n:
				print a
				i = i + 1
	print i