A Smith number is a composite number, the sum of whose digits is the sum of the digits of its prime factors obtained as a result of prime factorization (excluding 1 ). The first few such numbers are 4,22, 27, 58, 85, 94, and  121.

Example: 378=2 x 3 x 3 x 3 x 7
So, its prime factors are 2, 3, 3, 3, and 7 .
The sum of its digits is 3 + 7 + 8 = 18
The sum of the digits of its factors is 2+3+3+3+7 = 18.

Similarly,  4937775 is a Smith number.

Task: Write a program to check whether a given integer is a Smith number.

Input:

- There will be only one line of input: n(0<n<10⁹), the number which needs to be checked.

Output:

- print 1  if the number is a Smith number.

- print 0  if the number is not a Smith number.