Apok rất thích học tiếng anh nhưng cũng rất hay tìm hiểu về toán . Vào những ngày được nghỉ dịch ,apok lên mạng tìm hiểu ,vô tình cậu biết đến số chính phương .Chính phương là bình phương của 1 số tự nhiên .Apok biết 30/11 là cuộc thi của apok nên cậu muốn đố các bạn : Cho số ~ n ~ , hãy đếm xem có bao nhiêu số chính phương từ 1 tới ~ n ~ .

Input

Dòng 1 là số nguyên ~ t ~ (~ 1 \le t \le 10^5 ~);

~ t ~ dòng tiếp theo là số nguyên ~ n ~ (~ 1 \le n \le 10^{18} ~).

Output

Gồm ~ t ~ dòng là kết quả của bài toán .

Sample

Input #1

3
1
2
4

Output #1

1
1
2