題目：（AcWing）

給定?n?個正整數?ai，請你求出每個數的歐拉函數。

歐拉函數的定義

1～N?中與?N?互質的數的個數被稱為歐拉函數，記為??(N)。
若在算數基本定理中，N=，則：
?(N)?=?N×

輸入格式

第一行包含整數?n。

接下來?n行，每行包含一個正整數?ai。

輸出格式

輸出共?n行，每行輸出一個正整數?ai的歐拉函數。

數據范圍

1≤n≤100
1≤ai≤2×109

輸入樣例：

3
3
6
8

輸出樣例：

2
2
4

代碼實現：

#include <iostream>
using namespace std;
int main()
{int n;cin>>n;while(n--){int a;cin>>a;int res = a;for(int i = 2;i<= a/i ;i++){if(a % i == 0){res=res/i*(i-1);while(a%i == 0) a/=i;}}if(a > 1) res = res/a*(a-1);cout << res <<endl;}return 0;
}