def factor(n):
	d = 2
	factors = [ ]
	while n >= d*d:
		if n % d == 0:
			n = n/d
			factors.append(d)
		else:
			d = d + 1
	if n > 1:
		factors.append(n)
	return factors

def euler(n):
	A=factor(n)
	l=len(A)
	phi=1
	if l==0:
		return 1
	p=1
	for i in range(0,l):
		if A[i]!=p:
			p=A[i]
			phi=phi*(p-1)
		else:
			phi=phi*p
	return phi,A