时间限制：1000ms　内存限制：512MB

题目描述

程老师管理着一个大型实验室，里面摆满了各种设备和仪器。为了方便管理，他决定给每台设备编一个工号。工号不是随便编的，程老师定了一套规则：

1. 工号必须是正整数；
2. 工号必须是"稳固数"，也就是素数（质数）。素数是指大于 1 且只能被 1 和自身整除的正整数；
3. 光是素数还不够。程老师又加了一条：工号必须是"双重稳固数"，也就是说，这个数本身是素数，并且它的十进制表示中各位数字之和也是素数。两个条件缺一不可。

实验室的设备是一批一批采购回来的。每当一批新设备到货，程老师会为这批设备划定一个候选区间 $[l, r]$（包含 $l$ 和 $r$ 两个端点），然后从中挑选一个工号，分配给这批设备里最重要的那台仪器。挑选的方式很固定：把区间内所有双重稳固数从小到大依次排出来，取其中的第 $k$ 个。

如果区间内的双重稳固数总数不足 $k$ 个，这一次就挑不出工号，程老师会记下一个 $-1$，作为这次挑选的结果，这台仪器只能等下一批再编。

这样的挑选一共进行了 $q$ 次。每次挑选给出三个整数 $l, r, k$，请你告诉程老师这一次挑选的结果：区间 $[l, r]$ 内第 $k$ 小的双重稳固数；如果不存在，就告诉他 $-1$。各次挑选相互独立，互不影响。

输入格式

第一行一个整数 $q$，表示挑选次数。

接下来 $q$ 行，每行三个整数 $l, r, k$，表示一次挑选的候选区间 $[l, r]$ 和序号 $k$。

输出格式

对于每次挑选，输出一行一个整数：区间 $[l, r]$ 内第 $k$ 小的双重稳固数；如果区间内双重稳固数不足 $k$ 个，输出 $-1$。

数据范围

特殊性质 A：所有挑选的 $k = 1$。

对于所有数据，$1 \le q \le 10^5$，$1 \le l \le r \le 10^6$，$1 \le k \le 10^9$。

样例

样例 1 输入

5
1 10 3
11 30 2
20 50 5
5 20 4
7 7 1

样例 1 输出

5
23
47
-1
7

样例 2 输入

4
100 200 1
100 200 5
100 200 25
100 200 13

样例 2 输出

101
139
-1
199

样例 1 解释

第 2 次挑选中，区间 $[11, 30]$ 内的双重稳固数依次是 $11$、$23$、$29$，第 $2$ 个是 $23$；第 4 次挑选中，区间 $[5, 20]$ 内只有 $5$、$7$、$11$ 共 $3$ 个双重稳固数，不足 $4$ 个，输出 $-1$。