Find the Euler Totient Function (ETF) Φ(N) for an input N. ETF is the count of numbers in {1, 2, 3, …, N} that are relatively prime to N, i.e., the numbers whose GCD (Greatest Common Divisor) with N is 1.
 
Example 1:
Input:
N = 11
Output:
10
Explanation:
From 1 to 11,
1,2,3,4,5,6,7,8,9,10
are relatively prime to 11.
Example 2:
Input:
N = 16
Output:
8
Explanation:
From 1 to 16
1,3,5,7,9,11,13,15 
are relatively prime
to 16.
Your Task:
You don't need to read input or print anything. Your task is to complete the function ETF() which takes one integer value N, as input parameter and return the value of Φ(N).
 
Expected Time Complexity: O(NLog N)
Expected Space Complexity: O(1)
 
Constraints:
1<=N<=10^{5}

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3
class Solution:
    def ETF (self, N):
        # code here

Solutions:
class Solution:

	def ETF(self, N):
		x = N
		p = 2
		ans = N
		while p * p <= N:
			if x % p == 0:
				while x % p == 0:
					x = x // p
				ans = ans * (p - 1) // p
			p += 1
		if x > 1:
			ans = ans * (x - 1) // x
		return ans


class Solution:

	def ETF(self, n):

		def prime(n):
			i = 2
			temp = n
			t = n
			while i * i <= n:
				if n % i == 0:
					temp -= temp // i
				while n % i == 0:
					n //= i
				i += 1
			if n > 1:
				temp -= temp // n
			return temp
		return prime(n)


class Solution:

	def ETF(self, N):
		result = N
		p = 2
		while p * p <= N:
			if N % p == 0:
				while N % p == 0:
					N = N / p
				result *= 1.0 - 1.0 / p
			p += 1
		if N > 1:
			result *= 1.0 - 1.0 / N
		return int(result)


class Solution:

	def ETF(self, n):
		primes = set()
		c = int(2)
		temp = int(n)
		while temp > 1:
			if temp % c == 0:
				primes.add(c)
				temp = temp / c
			else:
				c += 1
		ans = n
		for i in primes:
			ans = int(ans * (1 - 1 / i))
		return ans


class Solution:

	def ETF(self, n):
		result = n
		p = 2
		while p * p <= n:
			if n % p == 0:
				while n % p == 0:
					n = n // p
				result = result * (1.0 - 1.0 / float(p))
			p = p + 1
		if n > 1:
			result -= result // n
		return int(result)


class Solution:

	def ETF(self, n):
		result = n
		for i in range(2, n):
			if n % i == 0:
				while n % i == 0:
					n = n // i
				result = result * (1.0 - 1.0 / float(i))
		if n > 1:
			result = n - 1
		return int(result)


class Solution:

	def ETF(self, N):
		k = 2
		m = {}
		Q = N
		while k * k <= N:
			while Q % k == 0:
				if k in m:
					m[k] += 1
				else:
					m[k] = 1
				Q = Q // k
			k += 1
		if Q != 1:
			m[Q] = 1
		p = N
		for i in m:
			p *= 1 - 1 / i
		return int(p)


import math

class Solution:

	def ETF(self, N):
		x = N
		i = 2
		ans = N
		while i * i <= N:
			if x % i == 0:
				while x % i == 0:
					x = x // i
				ans = ans * (i - 1) // i
			i += 1
		if x > 1:
			ans = ans * (x - 1) // x
		return ans


class Solution:

	def ETF(self, n):
		count = n
		i = 2
		while i * i <= n:
			if n % i == 0:
				count = count - count // i
				while n % i == 0:
					n = n // i
			i += 1
		if n > 1:
			count = count - count // n
		return count


class Solution:

	def ETF(self, N):
		x = N
		i = 2
		ans = N
		while i * i <= N:
			if x % i == 0:
				while x % i == 0:
					x = x // i
				ans = ans * (i - 1) // i
			i += 1
		if x > 1:
			ans = ans * (x - 1) // x
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.ETF(N))


from math import sqrt

class Solution:

	def ETF(self, N):
		x = N
		i = 2
		while i * i <= N:
			if N % i == 0:
				x /= i
				x *= i - 1
				while N % i == 0:
					N /= i
			i += 1
		if N > 1:
			x /= N
			x *= N - 1
		return int(x)


class Solution:

	def ETF(self, N):
		p = 2
		cnt = N
		while p * p <= N:
			if not N % p:
				while not N % p:
					N //= p
				cnt *= 1 - 1 / p
			p += 1
		if N > 1:
			cnt *= 1 - 1 / N
		return int(cnt)


class Solution:

	def ETF(self, N):
		count = N
		p = 2
		while p * p <= N:
			if N % p == 0:
				while N % p == 0:
					N = N // p
				count = count * (1.0 - 1.0 / float(p))
			p += 1
		if N > 1:
			count = count * (1.0 - 1.0 / float(N))
		return int(count)


class Solution:

	def ETF(self, N):

		def gcd(x, y):
			if y == 0:
				return x
			return gcd(y, x % y)

		def solve(n):
			ct = 0
			for x in range(1, n):
				if gcd(n, x) == 1:
					ct += 1
			return ct

		def phi(n):
			res = n
			p = 2
			while p * p <= n:
				if n % p == 0:
					while n % p == 0:
						n = int(n / p)
					res -= int(res / p)
				p += 1
			if n > 1:
				res -= int(res / n)
			return res
		return phi(N)