Mirko and his older brother Slavko are playing a game. At the beginning of the game, they pick three numbers . In the first and only step of the game, each of them picks their own consecutive integers.
Slavko always picks the first integers (numbers ). Mirko has a special demand – he wants to choose his numbers in a way that there are exactly happy numbers among them. He considers a number happy if it meets at least one of the following requirements:
- the number is smaller than or equal to .
- the number is prime.
Out of respect to his older brother, will be smaller than or equal to the total number of happy numbers in Slavko's array of numbers.
They will play a total of games with different values . For each game, help Mirko find an array that meets his demand.
Input
The first line of input contains . Each of the following lines contains three integers, the line containing integers that determine the values that will be used in the game.
Output
Output lines, the line containing an integer, the initial number of Mirko's array in the game.
If an array with the initial number being smaller than or equal to does not exist, output
-1
. If there are multiple possible solutions, output any.
Sample Input 1
3
1 1 1
2 0 2
3 1 1
Sample Output 1
1
8
4
Sample Input 2
3
4 1 1
5 2 3
5 0 3
Sample Output 2
6
4
24
Sample Input 3
4
7 2 5
6 1 1
10 4 5
6 2 2
Sample Output 3
6
20
5
4
Comments