题目描述

小蓝在研究一种特殊的质数。

对于一个正整数，将它十进制表示中所有数位上的数字相加，即可得到它的数位和。如果这个正整数同时满足以下两个条件，小蓝就称它为“方和质数”：

• 这个数是质数；
• 这个数的数位和是完全平方数。

例如，$13$ 的数位和为 $1 + 3 = 4 = 2^2$，且 $13$ 是质数，因此 $13$ 是方和质数。

现在，给定区间 $[L, R]$ 和正整数 $K$，请你找出区间 $[L, R]$ 内从小到大排列的第 $K$ 个方和质数。若区间内的方和质数不足 $K$ 个，则输出 $-1$。

输入格式

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

输出格式

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

2 100 3

79

2 10 1

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