Cho số nguyên dương a . Hãy đếm xem có bao nhiêu số tự nhiên b ~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<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

dòng, mỗi dòng là đáp án cho một truy vấn