P16800 [蓝桥杯 2026 国 B] 方和质数

小蓝在研究一种特殊的质数。 对于一个正整数，将它十进制表示中所有数位上的数字相加，即可得到它的数位和。如果这个正整数同时满足以下两个条件，小蓝就称它为“方和质数”： - 这个数是质数； - 这个数的数位和是完全平方数。 例如，$13$ 的数位和为 $1 + 3 = 4 = 2^2$，且 $13$ 是质数，因此 $13$ 是方和质数。 现在，给定区间 $[L, R]$ 和正整数 $K$，请你找出区间 $[L, R]$ 内从小到大排列的第 $K$ 个方和质数。若区间内的方和质数不足 $K$ 个，则输出 $-1$。

输入一行，包含三个整数 $L, R, K$。

输出一行，一个整数，表示区间 $[L, R]$ 内第 $K$ 个方和质数；若不存在，则输出 $-1$。

### 【样例说明 1】 区间 $[2, 100]$ 内的方和质数依次为 $13, 31, 79, 97$，因此第 $3$ 个为 $79$。 ### 【样例说明 2】 区间 $[2, 10]$ 内的质数为 $2, 3, 5, 7$，它们的数位和分别为 $2, 3, 5, 7$，均不是完全平方数，因此输出 $-1$。 ### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$1 \le L \le R \le 10^6$，$1 \le K \le 10^4$。 对于所有评测用例，$1 \le L \le R \le 10^{12}$，$R - L + 1 \le 10^6$，$1 \le K \le 10^6$。