Lại là Lật mặt các đồng xu

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 10M
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

Toto học toán lớp 5 năm nay thi vào lớp 6 có bài toán như sau.

Cho n đồng xu đánh số thứ tự từ 1 đến n, ban đầu tất cả các đồng xu đều ngửa, Toto thực hiện n bước biến đổi

Bước 1: Lật mặt ngược lại những đồng xu có số thứ tự chia hết cho 1

Bước 2: Lật mặt ngược lại những đồng xu có số thứ tự chia hết cho 2

...

Bước n: Lật mặt ngược lại những đồng xu có số thứ tự chia hết cho n

Sau quá trình lật mặt các đồng xu n bước như vậy hỏi có bao nhiêu đồng xu ngửa

Toto đau đầu quá nhờ các bạn tính giúp Toto với

Input

Dòng đầu là số bộ kiểm thử t(1≤t≤1000)

Dòng tiếp theo chứa t số nguyên dương có giá trị không vượt quá 1018

Output

Với mỗi trường hợp kiểm thử bạn xuất ra một kết quả trên một dòng

Ví dụ

Input

Copy
2
7 2020

Output

Copy
5
1976

Giải thích : với số đồng xu bằng 7 ta quy ước N là ngửa và X là xấp ta có

Khởi tạo: N N N N N N N

Bước 1: X X X X X X X

Bước 2: X N X N X N X

Bước 3: X N N N X X X

Bước 4: X N N X X X X

Bước 5: X N N X N X X

Bước 6: X N N X N N X

Bước 7: X N N X N N N

Kết thúc bước 7 ta có 5 đồng xu ngửa

Chú ý Đây là bản khó, bản dễ hơn xem tại Lật mặt các đồng xu

tichpx

Comments


  • 1
    No_Limit  commented on Jan. 9, 2023, 7:45 a.m.

    mặt thứ i xấp <--> i có số ước lẻ -> số mặt ngửa = n- tất cả các số là số chính phương [1,n]


  • 0
    ChuBbling  commented on Sept. 15, 2021, 11:18 a.m.

    TICHPX thầy có thể xem test 1 với 2 sao em sai được không ạ