思路

这个问题的核心是生成 $x$ 的各位数字的全排列，并对每个排列出的数字进行验证。由于 $x$ 的最大值为 $10^9$，它最多有 $10$ 位数字。$10$ 个不同数字的全排列数量是 $10!$（约为 $360$ 万），这是一个在现代计算机上可以接受的计算量。因此，我们可以采用直接模拟的方法：生成所有排列，然后逐一检查。

具体思路步骤如下：

1. 预处理：

   • 将整数 $x$ 转换为数字字符的集合（例如，字符串或字符数组），方便进行排列操作。设其长度为 $N$。
   • 找出 $x$ 的所有不同质因数。这是为了高效地检查条件 $\gcd(x, y) > 1$。两个数最大公约数大于 $1$，等价于它们拥有至少一个共同的质因数。因此，我们只需要检查 $y$ 是否能被 $x$ 的任何一个质因数整除即可。

题目内容

小红给定一个数字 $x$ ，现在她准备把其数位上的数字重新排列，满足重排后的数字没有前导零并且和原数字不同，例如 $x=213$ ，重排后可以是 $[123,132,231,312,321]$，但不能是 $213$ ，因为和原数字相同。例如 $x=224$ ，重排后一共有 $[242,422]$ ，两种可能。又例如 $10$ ，其不存在符合要求的重排后的数字，因为仅存在 $[10,01]$ ，和原数字相同或存在前导 $0$ ，都不构成合法数字。

现在请你帮助小红计算有多少个重排后的数字 $y$，使得 $gcd(x,y)≠ 1$ 。

$gcd$ ，即最大公约数，指两个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大 约数是 $6$ ，因此 $gcd(12,30)=6$ 。

输入描述

一个整数 $x(1 ≦ x ≦ 10^9)$ ，表示给定的数字。

输出描述

一个整数，表示满足条件的重排数字的数量。

样例1

输入

213

输出

5

样例2

输入

10

输出

0

样例3

输入

224

输出

2