Hiệu lập phương

View as PDF




Time limit:
Python 3 5.0s

Author:
Problem type
Points: 100 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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

Comments