Is There a Divisor?

Time limit2sMemory limit512 MB

Summary

Given a digit string, find a base B and a divisor X (both at most 10^9) making the string's value composite in base B, or report that none exists.

Level: Medium6 of 10
Topics: Math, Number theory, String, Brute force
Solved: No attempts yet

Problem

A forum that discusses informatics olympiad problems introduced the following captcha. A participant is given a string of $N$ decimal digits (with no leading zeros). In reply, the participant must enter a base $B$ such that in this base the given record represents a composite number (call it $D$ ), along with a number $X$ that is greater than 1, less than $D$ , and a divisor of $D$ .

Here $B$ and $X$ must not exceed $10^9$ .

Given a string of decimal digits, find any pair of numbers $B$ and $X$ that satisfies the constraints, or report that no solution exists within the given constraints.

Input

The input consists of a single non-empty string of at most $3 \cdot 10^6$ characters made up of digits from 0 to 9 that does not begin with 0.

Output

If a solution exists, output two numbers: the base $B$ and the divisor $X$ , written in decimal. Both numbers must satisfy $2 \le B,X \le 10^9$ . If no solution exists, output $-1$ .

Examples3

Example 1
Input
```
1
```
Expected output
```
-1
```
Example 2
Input
```
4
```
Expected output
```
10 2
```
Example 3
Input
```
19
```
Expected output
```
11 2
```