Số LTN

Trong một ngôi làng nhỏ, có một truyền thuyết về hai con số kỳ diệu \(a\) và \(b\), được gọi là cặp số LTN. Theo truyền thuyết, cặp số này thỏa mãn điều kiện:

với \(X\) là một số nguyên dương được các trưởng làng lựa chọn cẩn thận.

Một ngày nọ, Eldric - cậu bé thông minh nhất làng - được giao nhiệm vụ giải mã bài toán LTN. Eldric cần phải tìm ra tất cả các cặp số \(a, b\) là cặp số LTN thỏa mãn điều kiện trên. Tuy nhiên, với số \(X\) lớn, nhiệm vụ này không hề dễ dàng.

\textbf Yêu cầu: Hãy giúp Eldric xác định có bao nhiêu cặp số \((a, b)\) thỏa mãn điều kiện của một cặp số LTN.

Input

• Dòng đầu tiên chứa một số nguyên \(T\) \((1 \leq T \leq 10^5)\), là số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(X\) \((1 \leq X \leq 10^6)\).

Output

• \(30\%\) số điểm ứng với \(1 \leq T \leq 10^3\), \(1 \leq X \leq 100\).
• \(30\%\) số điểm ứng với \(1 \leq T \leq 10^3\), \(1 \leq X \leq 10^6\).
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Example

1
2

6