P16800 [Lanqiao Cup 2026 National B] Square-Sum Prime

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 one line containing three integers $L, R, K$.

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$.

### 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