Cho số nguyên dương \(a\). Hãy đếm xem có bao nhiêu số tự nhiên \(b < a\) mà \(a^3 - b^3\) là số nguyên tố.

Input

• Dòng đầu tiên chứa một số nguyên dương \(q \ (q \leq 100)\), số lượng truy vấn cần trả lời.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a\).

Output

• In ra \(q\) dòng, mỗi dòng là đáp án cho một truy vấn

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(a \leq 200\)
• Subtask \(2\) (\(30\%\) số điểm): \(a \leq 2000\)
• Subtask \(3\) (\(40\%\) số điểm): \(a \leq 10^6\)

Example

3
1
2
3

0
1
1