Số những số nguyên tố cùng nhau

Submit solution
Points: 2 (partial)
Time limit: 2.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Cho số nguyên dương n hãy đếm những số nguyên dương trong đoạn [1,n] nguyên tố cùng nhau với n

Input

Dòng đầu là số bộ test t(1≤t≤104)

Tiếp theo gồm t dòng mỗi dòng chứa đúng một số nguyên dương n(1<n≤109)

Output

Gồm t dòng mỗi dòng chứa đúng một số nguyên dương là số những số nguyên dương nhỏ hơn n nguyên tố cùng nhau với n

Ví dụ

Input

Copy
2
9
10

Output

Copy
6
4

Giải thích

Với n=9 có 6 số nguyên tố cùng nhau với 9 trong đoạn [1,9] là 1,2,4,5,7,8

Với n=10 có 4 số nguyên tố cùng nhau với 10 trong đoạn [1,10] là 1,3,7,9

tichpx

Comments


  • 1
    TICHPX  commented on March 28, 2020, 8:05 a.m.

    Hàm Phi Euler