Hiệu lập phương

Xem PDF
Thời gian:
Python 3 5.0s
Tác giả:
cuom1999
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input 
3
1
2
3
Output 
0
1
1
Note
  • Trong ví dụ 1, \(b\) có thể bằng 0. Tuy nhiên \(1^3-0^3=1\) không phải số nguyên tố.
  • Trong ví du 2, \(b = 0\) hoặc \(1\). Khi đó, \(a^3-b^3=8\) hoặc \(7\). Đáp số là \(1\) vì \(7\) là số nguyên tố.

Bình luận