Next prime after n

Problem

A lottery stall gives out ticket numbers that are prime. Read n and print the smallest prime number that is strictly greater than n.

Example 1

Input

Output

101 is prime.

Example 2

Input

Output

"Greater than" means 13 itself does not count: the answer is 17.

Try the problem first. Open one hint at a time.

Hint 1

Try candidates n + 1, n + 2, ... one by one, and stop at the first prime.

Hint 2

Inside, check a candidate with the √ test from "Prime number check".

Hint 3

The outer loop can be while (true) with a break once a prime is found.

Write your Java code, run it on the examples and submit it to hidden tests.