Intersection Set of Prime Factors

题目描述

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≤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.

样例 #1

样例输入 #1

623457198

样例输出 #1

4 123457698

提示

There are two $m's$ with $4$ common factors. Besides the one given in the problem description, we can also swap $6$ and $1$ to obtain $123457698$. This number has a prime factor set $\{2, 3, 7, 13, 23, 29, 113\}$, and so the intersection set is also $\{2, 3, 7, 13\}$. This number is in the ouput because it is smaller than $693457128$.