Given a nonnegative integer a, and a positive integer N, we define: f(a, 1) = a f(a, k) = f(a, k ¨C 1) * f(a, k ¨C 1) % N, k > 1 There may or may not exist some positive integer k satisfying f(a, k) = 0. Your task is, given a positive integer N, to determine how many a (0<= a <= N) there are, such that for some positive integer k, f(a, k) = 0. Input The input contains an integer T on the first line, indicating the number of test cases. Each test case contains only one positive integer N(1<=N<=1000000000) on a line. Output For each test case, output the answer on a single line. Sample Input 6 2 12 50 180 245 361 Sample Output 2 3 6 7 8 20 Source UESTC 5th programming contest