## Prime Product

Statement

## Goal

A prime product is a positive integer that is the product of exactly two prime numbers greater than 1. For example, 22 is a prime product since 22 = 2 * 11 and both 2 and 11 are prime numbers.Write a program to print the closest prime product to an integer

`n`. Note that

`n`itself can be a prime product, and in that case, print

`n`.

(

`n`is a positive integer that is only divisible by 1 and

`n`

Note that 0 and 1 are not considered prime numbers.

Input

A single integer

`n`.Output

A single line containing the closest prime product to the given integer

`n`.Constraints

2 ≤

There will always be only 1 possible solution

`n`≤ 200There will always be only 1 possible solution

Example

Input

23

Output

22

Game modes

Fastest, Shortest

Test cases

Test 1 Test

Input

23

Output

22

Validator 1 Validator

Input

20

Output

21

Test 2 Test

Input

35

Output

35

Validator 2 Validator

Input

49

Output

49

Test 3 Test

Input

28

Output

26

Validator 3 Validator

Input

100

Output

95

Test 4 Test

Input

164

Output

166

Validator 4 Validator

Input

200

Output

201

Beware of low n Test

Input

2

Output

4

Validator 5 Validator

Input

3

Output

4

Test 6 Test

Input

170

Output

169

Validator 6 Validator

Input

19

Output

21

Test 7 Test

Input

189

Output

187

Validator 7 Validator

Input

40

Output

39

Test 8 Test

Input

22

Output

22

Validator 8 Validator

Input

119

Output

119

Solution language

Solution

Stub generator input

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants