Lại là Lật mặt các đồng xu
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 2020Output
5
1976Giả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
Comments
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]
TICHPX thầy có thể xem test 1 với 2 sao em sai được không ạ