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

题目描述

给定一个正整数 $n$，任选其十进制表示中某两位不同的数字交换位置，得到另一个整数 $m$。问 $m$ 的质因数集合与 $n$ 的质因数集合有多大交集？ 例如 $n=623457198$ 时，我们可以算出其质因数集合为 A = {2, 3, 7, 13, 380621}。如果将 2 和 9 交换得到 $m=693457128$，其质因数集合为 B = {2, 3, 7, 13, 109, 971}。则 A 和 B 的交集为 {2, 3, 7, 13}，有 4 个因子。

输入格式

输入在一行中给出一个正整数 $n$（$10<n \le 10^9$）。题目保证 $n$ 至少有 2 个位置上的数字不相等。

输出格式

将 $n$ 的任意两位不同数字交换位置后得到数字 $m$，找到其质因数集合与 $n$ 的质因数集合有最大交集的那个 $m$。在一行中输出交集中质因子的个数和 $m$，其间以 1 个空格分隔。如果这样的 $m$ 不唯一，则输出数值最小者。

样例

623457198

4 123457698

限制

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