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


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 10M

Author:
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 \le t \le 1000)\)

Dòng tiếp theo chứa \(t\) số nguyên dương có giá trị không vượt quá \(10^{18}\)

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

2
7 2020

Output

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 ạ