Problem Description

Xiao Lan is studying a special kind of prime number.

For a positive integer, add up all digits in its decimal representation to get its digit sum. If this positive integer satisfies both of the following conditions, Xiao Lan calls it a “square-sum prime”:

• The number is a prime number.
• The digit sum of the number is a perfect square.

For example, the digit sum of $13$ is $1 + 3 = 4 = 2^2$, and $13$ is a prime number, so $13$ is a square-sum prime.

Now, given an interval $[L, R]$ and a positive integer $K$, find the $K$-th square-sum prime in the interval $[L, R]$ when sorted in increasing order. If there are fewer than $K$ square-sum primes in the interval, output $-1$.

Input Format

Input one line containing three integers $L, R, K$.

Output Format

Output one line with one integer, representing the $K$-th square-sum prime in the interval $[L, R]$. If it does not exist, output $-1$.

2 100 3

79

2 10 1

-1

Hint

Sample Explanation 1

The square-sum primes in the interval $[2, 100]$ are $13, 31, 79, 97$ in order, so the $3$-rd one is $79$.

Sample Explanation 2

The prime numbers in the interval $[2, 10]$ are $2, 3, 5, 7$. Their digit sums are $2, 3, 5, 7$, none of which are perfect squares, so output $-1$.

Constraints

For $30\%$ of the testdata, $1 \le L \le R \le 10^6$, $1 \le K \le 10^4$.

For all testdata, $1 \le L \le R \le 10^{12}$, $R - L + 1 \le 10^6$, $1 \le K \le 10^6$.

Translated by ChatGPT 5