该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Given a positive integer $n$. Select two distinct digits from the decimal repersentation（十进制表示）of $n$, we obtain another integer $m$. What is the size of the intersection set（交集）of the prime factors of $n$ and $m$? For example, given $n=623457198$, its prime factor set is A = {2, 3, 7, 13, 380621}. Swapping 2 and 9 gives us $m=693457128$, of which the prime factor set is B = {2, 3, 7, 13, 109, 971}. Then the intersection set of A and B is {2, 3, 7, 13}, with 4 factors.

输入格式

Each input file contains one test case, which gives a positive integer $n$ ($10<n \le 10^9$). It is guaranteed that there are at least 2 distinct digits in $n$.

输出格式

Swap any pair of digits in $n$ to obtain $m$, you are supposed to find the $m$ with the largest intersection set of the prime factors of $n$ and $m$. Output in a line the number of the prime factors in the intersection set, together with $m$. The numbers must be separated by 1 space, and there must be no extra space at the beginning or the end of the line. In case such an $m$ is not unique, output the one with the smallest value.

样例

623457198

4 123457698

限制

对于所有的测试用例,限制为400ms, 64MB