Square-Substring-Free Number

Time limit1sMemory limit1024 MB

Summary

Given N up to 10^18, find the smallest number at least N whose decimal representation contains no perfect square as a substring.

Level: Hard8 of 10
Topics: Dynamic programming, String matching, Greedy
Solved: No attempts yet

Problem

For an integer $a$ , write $a^2$ in decimal notation. A positive integer $N$ is called a square-substring-free number if none of those decimal strings appears as a substring of the decimal representation of $N$ .

In increasing order, these numbers begin as $2, 3, 5, 6, 7, 8, 22, 23, 26, \ldots$ .

Given a positive integer $N$ , find the smallest square-substring-free number that is at least $N$ .

Input

A positive integer $N$ is given.

$1 \le N \le 10^{18}$

Output

Print the smallest square-substring-free number that is at least $N$ .

Examples3

Example 1
Input
```
225
```
Expected output
```
226
```
Example 2
Input
```
545
```
Expected output
```
552
```
Example 3
Input
```
2356
```
Expected output
```
2356
```