Chef has decided to arrange the free shuttle service for his employees. City of Bhiwani has a strange layout - all of its N shuttle boarding points are arranged in a circle, numbered from 1 to N in clockwise direction. Chef's restaurant is at boarding point number 1. There is a single ring road that runs over the circumference of this circle and connects all the boarding points. There are also N - 1 different shuttle agencies available in Bhiwani.
For every different boarding points A and B there is exactly one shuttle that connects these points and it belongs to K^th shuttle agency where K is the distance between A and B in clockwise direction, that is, there are exactly K - 1 boarding points between points A and B in clockwise direction. Denote this shuttle as (A, B). So if N = 4, first agency has shuttles (1,2), (2,3), (3,4), (4,1), second agency has shuttles (1,3), (2,4) and the shuttles of third agency are (1,4), (2,1), (3,2), (4,3). If the shuttle connects points A and B, it is possible to go from A to B as well as from B to A using this shuttle.
Chef is planning to make a contract with one of the agencies so that all of his employees are able to travel in shuttles of that agency for free. He therefore wants to choose such a shuttle agency so that people from any boarding point can reach his restaurant only using shuttles of the chosen agency possibly using some intermediate boarding points. Your task is to find how many such shuttle agencies are there.

Input
First line contains an integer T denoting number of test cases. After that T lines follow each containing a single integer N denoting number of shuttle boarding points in Bhiwani.

Output
For every test case, output the number of shuttle agencies our chef could choose.

Constraints

1 ≤ T ≤ 100

2 ≤ N ≤ 10000

Example

Input:
3
2
3
4

Output:
1
2
2

Description:
In third case, there are 4 shuttle boarding points and there are 4 - 1 = 3 shuttle agencies. Using shuttles of only second agency, one can move between points (1,3) and points (2,4). So a person starting from point 2 can't reach restaurant using these shuttles. Each of the other two agencies connects all the points with the restaurant possibly through intermediate boarding points.

见题面

见题面