米尔科和他的哥哥Slavko玩一个游戏。在游戏开始时，他们选择三个号码k，L，M。在游戏的第一步和唯一步骤中，他们每个人都选择自己的k个连续整数。Slavko一直先选出K个整数（数字1, 2, ..., K）。米尔科有一个特殊的要求--他想在其中选择L个幸福的数字。他认为如果一个数字满足下列要求中的至少一个：
•数字小于或等于M
•数字是素数
出于对哥哥的尊敬, L将小于或等于Slavko数组里的总幸福数的数量。
他们将玩Q场游戏伴随着不同的K，L，M的值.每一场游戏, 帮助米尔科找到满足他的要求的数组。
输入:
第一行整数Q(1≤Q≤100000)
接下来的Q行每一行包括三个整数，第ith行包含整数Ki，Li，Mi，（1≤Ki，Mi≤1500≤Li≤Ki），确定了k，L，M用于在第ith场游戏的值。
输出：
输出Q行，第ith行包含一个整数，在这场游戏中米尔科数组的初始数。如果没有初始数小于或等于10 000 000的数组存在，输出-1。如果有多个可能的解决方案，输出任意一个。
样例：

Input  
3
1 1 1
2 0 2
3 1 1
Output
1
8
4

Input
3
4 1 1
5 2 3
5 0 3
Output
6
4
24

Input
4
7 2 5
6 1 1
10 4 5
6 2 2
Output
6
20
5
4