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 Kth 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.I designed the code to solve this problem but I am not sure about the correct answers.
if someone could confirm me the answers for n=10000 is 4000 and n=1000 400 and n=15 8.Then I can be sure about it
thanks.