Encoding_January_Chefu and Tiles

Chefu is an interior designer and often gets a contract to decorate the floor of the house with tiles.
Chefu is in demand because of his unusual design.If N is the total no of tiles required for 
the floor, for every i≤N where i and N are co-prime,Chefu puts a Black tile or else White tile.

As Chefu is in demand, he want u to help him with number of Black tile needed for the floor.

Input:
First-line will contain T, the number of test cases. Then the test case follows.
Each test case contains a single input N.
Output:
For each test case, print the total numbers of black tiles required

Constraints
1≤T≤1000
1≤N≤106
Sample Input:
3
9
166
321
Sample Output:
6
82
212
Author:	3★akay_99
Tags:	akay_99
Date Added:	14-01-2020
Time Limit:	1 secs
Source Limit:	50000 Bytes
Languages:	C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB


Problem Solution:--- 

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
			sieve();
		FastReader sc=new FastReader(System.in);
		StringBuilder sb=new StringBuilder();
		int t=sc.nextInt();
		while(t-->0)
		{
			int n=sc.nextInt();
			sb.append(phi(n)).append("\n");
			
			
		}
		System.out.println(sb);
	}
	static int MAX = 100001;  

	static ArrayList<Integer> p = new ArrayList<Integer>(); 
	  
	
	static void sieve()  
	{  
	    int[] isPrime=new int[MAX+1];  
	  
	    for (int i = 2; i<= MAX; i++)  
	    {  
	   
	        if (isPrime[i] == 0)  
	        {  
	           
	            p.add(i);  
	  
	           
	            for (int j = 2; i * j<= MAX; j++)  
	                isPrime[i * j]= 1;  
	        }  
	    }  
	}  
	  
	
	static int phi(int n)  
	{  
	    int res = n;  
	  
	 
	    for (int i=0; p.get(i)*p.get(i) <= n; i++)  
	    {  
	        if (n % p.get(i)== 0)  
	        {  
	     
	            res -= (res / p.get(i));  
	  
	          
	            while (n % p.get(i)== 0)  
	            n /= p.get(i);  
	        }  
	    }  
	  
	   
	    if (n > 1)  
	    res -= (res / n);  
	  
	    return res;  
	}  
}