Mùa đông đến, người người tà tưa, nhà nhà cafe. Quang đang quen một bạn gái cùng trường qua tính năng hẹn hò của facebook, cậu bèn mời bạn gái đi tà tưa đồng thời test thử IQ của bạn gái xem thế nào. Bạn gái đến quán tà tưa đúng giờ như đã hẹn với một vóc dáng rất xinh đẹp, ngay lập tức Quang bị hớp hồn, không ngờ còn xinh hơn cả ảnh trên face nữa kìa. Tuy vậy Quang vốn là người điềm tĩnh nên đã ngay lập tức kìm nén cảm xúc.

Đang trò chuyện vui vẻ, Quang bảo bạn gái là anh sẽ ra một câu đố, nếu em giải được, anh sẽ thưởng thêm bằng cách đưa em đi ăn kem trước cổng trường của một quán rất xịn xò. Bạn gái hứng khởi đồng ý.

Câu đố là: Cho một số nguyên dương \(0 < n \leq 10^{18}\). Em hãy tính xem có bao nhiêu số chính phương từ 1 tới \(n\). Quang không quên rút trong túi ra một chiếc máy tính casio fx 500000 ES thời thượng nhất cho bạn gái.

Các bạn hãy giúp bạn gái được ăn kem nhé.

Đầu vào:

• Dòng đầu tiên chứa số \(t\) là số lượng test (\(1\) \(\leq\) \(t\) \(\leq\) \(10\))
• T dòng tiếp theo mỗi dòng 1 số nguyên dương \(0\) \(<\) \(n\) \(<\) \(10^{18}\)

Đầu ra:

• \(T\) dòng, mỗi dòng 1 số là số lượng số chính phương từ 1 tới \(n\) tương ứng

Ví dụ:

Input

1
101

Output

10