{"code":"mokhoa","name":"Trò chơi với ổ khoá","description":"An có $n$ ổ khoá, và ban đầu tất cả ổ khoá này ở trạng thái khoá.\r\n\r\nVì ở nhà quá buồn chán, nên An quyến định đem $n$ chìa khoá này ra chơi, và quá trình chơi của anh ấy diễn ra như sau:\r\n\r\n+ Trò chơi, gồm có $n$ vòng, ở vòng thứ $i(1\\le i\\le n)$, anh ấy sẽ đổi trạng thái của tất cả những ổ khoá mà chia hết cho $i$, tức là ổ nào mở thì anh ấy khoá lại và ngược lại ! \r\n\r\nHỏi sau khi kết thúc $n$ vòng chơi, có bao nhiêu ổ khoá ở trạng thái mở \r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa số $t(1\\le t\\le 100)$ - Thể hiện số testcase \r\n\r\n+ $t$ dòng tiếp theo, mỗi dòng chứa số $n(1\\le n\\le 100.000.000)$\r\n\r\n

Output

\r\n\r\n+ Ứng với mỗi testcase, in ra đáp án cần tìm\r\n\r\n

Scoring

\r\n\r\n+ Subtask $1$ ($66.7\\%$ số điểm): $1\\le n\\le 100$\r\n+ Subtask $2$ ($16.65\\%$ số điểm): $100\\le n\\le 5000$\r\n+ Subtask $3$ ($16.65\\%$ số điểm): $5000\\le n\\le 100.000.000$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 2\r\n 3\r\n 5\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 1\r\n 2\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n + Giả sử ta kí hiệu: $0$- trạng thái mở và $1$- trạng thái khoá.\r\n - Xét testcase $1$, thì quá trình chơi sẽ diễn ra như sau: $(1,1,1)\\rightarrow (0,0,0) \\rightarrow (0,1,0) \\rightarrow (0,1,1)$ --> Do đó đáp án là $1$\r\n - Xét testcase $2$, thì quá trình chơi sẽ diễn ra như sau: $(1,1,1,1,1)\\rightarrow (0,0,0,0,0)\\rightarrow (0,1,0,1,0) \\rightarrow (0,1,1,1,0)\\rightarrow (0,1,1,0,0)\\rightarrow (0,1,1,0,1)$ --> Do đó đáp án là $2$.","points":250.0,"partial":false,"time_limit":5.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[34,36,37,14,28,38,39,18,17,29,23,27,35,25,26,19,32,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}