Happy Numbers

Time limit0.5sMemory limit64 MB

Summary

Find the smallest start of K consecutive integers with exactly L numbers that are at most M or prime, or output -1.

Level: Medium5 of 10
Topics: Number theory, Prefix sum, Sliding window
Solved: No attempts yet

Problem

Junhyung and Minhyung play a sequence game. Before the game starts, Minhyung picks three numbers $K$ , $L$ , and $M$ . Junhyung then has to say $K$ consecutive natural numbers.

Minhyung added one more rule to train Junhyung's mental arithmetic. Among the $K$ numbers Junhyung says, exactly $L$ of them must be happy numbers. A happy number is a number that meets at least one of the two conditions below.

It is a natural number not greater than $M$ .
It is a prime (a number with exactly 2 divisors).

Junhyung is slow at mental arithmetic, so he plans to work the answer out on a computer in secret. Write a program that answers Minhyung's questions.

Input

The first line contains the number of test cases $Q$ ( $1 \le Q \le 100\,000$ ).

Each of the next $Q$ lines contains $K$ , $L$ , and $M$ . ( $1 \le K, M \le 150$ , $0 \le L \le K$ )

Output

For each test case, print on one line the smallest of the $K$ numbers Junhyung says, that is, the starting value of the run of $K$ consecutive natural numbers. If several starting values satisfy the condition, print the smallest one. If no starting value satisfies the condition, or the smallest one is greater than 10,000,000, print -1.

Examples3

Example 1
Input
```
3
1 1 1
2 0 2
3 1 1
```
Expected output
```
1
8
4
```
Example 2
Input
```
3
4 1 1
5 2 3
5 0 3
```
Expected output
```
6
4
24
```
Example 3
Input
```
4
7 2 5
6 1 1
10 4 5
6 2 2
```
Expected output
```
6
20
5
4
```