CSES 3396 ↗

Next Prime

The smallest prime strictly greater than each given number.

1
submissions
1.000
best score

Given a positive integer n, find the next prime number after it.

Input

The first line has an integer t: the number of tests.

After that, each line has a positive integer n.

Output

For each test, print the next prime after n.

Constraints

  • 1≤t≤20
  • 1≤n≤1012

Example

Input:

5
1
2
3
42
1337

Output:

2
3
5
43
1361

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/NextPrime/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
4,343,077,8554,343,077,855

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.0004,343,077,855talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 13:31 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.