Cho một số nguyên dương ~n~. Với mỗi thao tác, bạn đặt ~n = \lfloor \sqrt{n} \rfloor~, với ~\lfloor i \rfloor~ là số nguyên lớn nhất không vượt quá ~i~. Đếm số thao tác để có ~n = 1~. Bạn cần phải xử lý nhiều bộ dữ liệu như vậy.

Dữ liệu vào

• Dòng đầu tiên gồm một số nguyên dương ~t~ ~(1 \le t \le 10^5)~ - số bộ dữ liệu.
• ~t~ dòng tiếp theo, mõi dòng gồm một số nguyên dương ~n~ ~(1 \le n \le 10^{18})~.

Dữ liệu ra

• Gồm ~t~ dòng, dòng thứ ~i~ là kết quả của bộ dữ liệu thứ ~i~.

Ví dụ

Ví dụ 1

Dữ liệu vào

2
10
20

Dữ liệu ra

2
3

Giải thích

• Với bộ dữ liệu đầu tiên, ~\lfloor \sqrt{10} \rfloor = 3~ và ~\lfloor \sqrt{3} \rfloor = 1~.
• Với bộ dữ liệu thứ hai, ~\lfloor \sqrt{20} \rfloor = 4~, ~\lfloor \sqrt{4} \rfloor = 2~ và ~\lfloor \sqrt{2} \rfloor = 1~.