KERNEL CRACKER

Trong khi kernel cracker uou đang bình yên vô sự với snxlgt_909, Prototype phát hiện ra một hệ thống fire wall và proxy tinh vi được bảo vệ bởi \(\mathrm{N}\) cổng logic mã hóa, đánh số từ \(\mathrm{1}\) đến \(\mathrm{N}\). Nơi đây chứa thông tin tuyệt mật của uou - một kernel cracker khét tiếng. Biết rằng IP address của uou gắn liền với snxlgt_909 để tiện lợi cho việc cracking. Nhưng Prototype đã phát hiện ra lỗ hổng mã hoá. Prototype mở các cuộc tấn công bằng cặp cổng \((i, j)\) ứng liền để có thể bẻ gãy được proxy và fire wall khiến uou lộ ví trí mà không bị phát hiện nếu tích chỉ số của hai cổng này \((i \times j)\) tạo thành một số chính phương. Nhằm chuẩn bị kịch bản tấn công tổng lực cho một hệ thống quy mô lớn có tới \(10^{18}\) cổng mã hoá và \(10^6\) firewall tiếp liền, hãy lập trình đếm xem có bao nhiêu cặp cổng logic \((i, j)\) mang lỗ hổng đối xứng này.

Vì để bẻ khoá quá khó, mà Prototype cần vượt qua \(10^6\) lần bẻ mới có thể biết được IP address của uou. Hãy giúp cậu ấy để khiến uou lộ vị trí nhé.

Yêu cầu: Với mỗi truy vấn \(N\), hãy đếm số cặp có thứ tự \((i, j)\) thỏa mãn \(1 ≤ i, j ≤ N\) và \(i × j\) là một số chính phương.

Input

• Dòng đầu chứa số nguyên dương \(\mathrm{Q}\) là số truy vấn
• \(Q\) dòng tiếp theo mỗi dòng nhập vào một số nguyên dương \(\mathrm{N}\)

Output

• Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất là số cặp \((i, j)\) tìm được trong khoảng từ \(1\) đến \(\mathrm{N}\)

Example

1
4

6

2
67
112

183
340

Ràng buộc

• \(Q ≤ 10^6\)
• \(N ≤ 10^{18}\)