Wonderprime Brands

Time limit1sMemory limit128 MB

Summary

Given D and N, find the smallest integer at least N whose digit string splits into two primes of length at least D, neither with a leading zero.

Level: Medium7 of 10
Topics: Number theory, Brute force, Math, Implementation
Solved: No attempts yet

Problem

The cows are forever competing to see who has the best brand, and the latest craze is a brand that is a "wonderprime". A brand is a sequence of digits that does not begin with $0$ , so it looks just like a positive integer.

A wonderprime is a positive integer whose digit string can be split into two consecutive parts — a left part and a right part, whose concatenation is the original number — such that both parts are prime, each part has at least $D$ digits, and neither part begins with $0$ .

For example, when $D=2$ , the number $11329$ is a wonderprime, because it splits into $113$ and $29$ , both of which are prime.

Given an integer $N$ , find the smallest wonderprime that is greater than or equal to $N$ . It is guaranteed that $1 \le N \le 2{,}000{,}000{,}000$ and that the answer never exceeds $2{,}000{,}000{,}000$ .

Input

The first line contains two space-separated integers $D$ and $N$ .

Output

Print the smallest wonderprime that is no smaller than $N$ .

Examples4

Example 1
Input
```
2 11328
```
Expected output
```
11329
```
Example 2
Input
```
2 11329
```
Expected output
```
11329
```
Example 3
Input
```
1 10
```
Expected output
```
22
```
Example 4
Input
```
2 1000
```
Expected output
```
1111
```