Counting X‐Primes in [1, 1,000,000]

For a positive integer \(N\) with \(M\) digits, we define a new number \(P\) as the number formed by deleting any \(K\) (\(0 \le K < M\)) digits from \(N\) (the remaining digits preserve their original order). If there exists at least one choice of digits to delete so that \(P\) is a prime number, then \(N\) is called an X‐prime.

For example, consider \(N=7869\). By deleting the digits \(7\) and \(6\) (i.e. \(K=2\)), we obtain \(P=89\), and since \(89\) is prime, \(7869\) is an X‐prime. Similarly, \(N=77\) is an X‐prime because by deleting one of its two digits, we get \(7\) which is prime.

Your task is to count how many different X‐primes exist in the range \(1 \le N \le 1{,}000{,}000\).

Note: When deleting digits, the order of the remaining digits does not change. Also, when a single digit is left, it is interpreted as its usual numerical value (for example, although 07 might appear, it is considered as \(7\)).

inputFormat

This problem does not require any input.

Note: The program should consider the range from \(1\) to \(1{,}000{,}000\) (inclusive).

outputFormat

Output a single integer representing the number of X‐primes in the range \(1 \le N \le 1{,}000{,}000\).

sample

995915