COCI '15 Contest 7 #5 Prosti

View as PDF

Submit solution


Points: 15
Time limit: 0.5s
Memory limit: 64M

Problem type

Mirko and his older brother Slavko are playing a game. At the beginning of the game, they pick three numbers K, L, M. In the first and only step of the game, each of them picks their own K consecutive integers.

Slavko always picks the first K integers (numbers 1, 2, \dots, K). Mirko has a special demand – he wants to choose his numbers in a way that there are exactly L 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 M.
  • the number is prime.

Out of respect to his older brother, L 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 Q games with different values K, L, M. For each game, help Mirko find an array that meets his demand.

Input

The first line of input contains Q (1 \le Q \le 100\,000). Each of the following Q lines contains three integers, the i^{th} line containing integers K_i, L_i, M_i (1 \le K_i, M_i \le 150, 0 \le L_i \le K_i) that determine the values K, L, M that will be used in the i^{th} game.

Output

Output Q lines, the i^{th} line containing an integer, the initial number of Mirko's array in the i^{th} game.

If an array with the initial number being smaller than or equal to 10\,000\,000 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

There are no comments at the moment.