소수 분할

양의 정수 N이 주어진다. N의 자릿수를 2개 이상의 부분으로 나누어, 각 부분이 모두 소수가 되도록 하는 방법의 수를 구하는 프로그램을 작성하시오.

예를 들어, 237의 경우 다음과 같이 나눌 수 있다:

• 2|3|7 (모두 소수)
• 2|37 (2와 37은 소수)
• 23|7 (23과 7은 소수)

따라서 237의 정답은 3이다.

입력

첫째 줄에 정수 N이 주어진다. (10 <= N <= 10^7)

출력

조건을 만족하는 분할 방법의 수를 출력한다. 방법이 없으면 0을 출력한다.

입출력 예시

입력 1

237

출력 1

3

입력 2

313

출력 2

2