TLEoj Contest #11 - Căn bậc hai về 0

Điểm: 1300 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

icebearlovecode

Dạng bài

Bạn được cho $1$ số nguyên dương $n$ và tại mỗi thao tác, bạn có thể trừ $n$ cho $\left \lfloor \sqrt n \right \rfloor$ . Nhiệm vụ của bạn là xác định số lượng thao tác cần thực hiện để $n = 0$ .

Ta có $\left \lfloor n \right \rfloor$ là phép làm tròn xuống. Ví dụ như $\left \lfloor 6.9 \right \rfloor=6,\left \lfloor 4.20 \right \rfloor=4$ .

Input, Output và Subtasks

Input

Dòng đầu chứa số nguyên dương $t$ là số testcase $(1\le t\le 10^5)$ .
$t$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $n$ $(1\le n\le 10^{18})$ .

Output

Xuất ra $t$ dòng, mỗi dòng xuất ra kết quả tương ứng trên một dòng.

Scoring

Subtask $1$ ( $10\%$ ): $n\le 10^6$ .
Subtask $2$ ( $90\%$ ): Không có ràng buộc gì thêm.

Sample

Input

Output

Bình luận

Không có bình luận nào.