package main
import "fmt"
import "bufio"
import "os"

var reader=bufio.NewReader(os.Stdin)
var writer=bufio.NewWriter(os.Stdout)

// prime 质数分解
func prime(n int) []int {
    var d []int
    for i:=2;i<=n/i;i++{
        if n%i == 0 {
            d=append(d, i)
            n/=i
            for n%i==0{
                n/=i
            }
        }
    }
    if n>1{
        d=append(d,n)
    }
    return d
}

// euler 欧拉函数 求 1~n 互质的数个数
func euler(n int) int {
    res:=n
    for _,x:=range prime(n){
        res/=x
        res*=x-1
    }
    return res
}

func main(){
    var n int
    fmt.Fscan(reader, &n)
    var a int
    for i:=0;i<n;i++{
        fmt.Fscan(reader, &a)
        fmt.Fprintln(writer, euler(a))
    }
    writer.Flush()
}