## ETF - Euler Totient Function

Đọc đề đẹp hơn ở:

https://codeforces.com/group/FLVn1Sc504/contest/274491/problem/D

https://codeforces.com/group/FLVn1Sc504/contest/274491/problem/D

In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 <= n <= 10^6). Compute the value of the totient φ.

### Input

First line contains an integer T, the number of test cases. (T <= 20000)

T following lines, each contains an integer n.

### Output

T lines, one for the result of each test case.

### Example

Input:5 1 2 3 4 5Output:1 1 2 2 4

Added by: | Race with time |

Date: | 2009-03-27 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |