시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 64 MB 20 7 6 50.000%

문제

준형이와 민형이가 수열 게임을 한다. 게임을 시작하기에 앞서, 민형이는 K, L, M 3개의 수를 뽑는다. 민형이가 수를 뽑았다면, 준형이는 K개의 연속한 자연수를 말해야 한다.

민형이는 준형이의 암산 실력을 키우기 위해서 룰을 하나 추가했다. 이 룰에 따르면, 준형이가 K개의 수를 말하면 그 중에서 '행복한 수'가 정확히 L개 있어야 한다. 행복한 수는 아래 두 조건 중 하나 이상을 만족시키는 수를 말한다.

  • 수가 M 이하의 자연수인 경우
  • 수가 소수(약수가 정확히 2개인 수)인 경우

준형이는 민형이의 질문에 빠른 대답을 하지 못하기 때문에 몰래 컴퓨터를 이용해서 답을 하려고 한다. 민형이의 질문에 답을 해주는 프로그램을 작성하여라.

입력

첫 번째 줄에는 테스트 케이스의 수 Q (1 ≤ Q ≤ 100 000)가 주어진다.

두 번째 줄부터 Q개의 줄에는 K, L, M의 값이 주어진다. (1 ≤ K, M ≤ 150, 0 ≤ L ≤ K)

출력

Q개의 줄에 준형이가 말해야 할 K개의 수들 중 가장 작은 수를 출력한다. 만약 답이 없거나 10 000 000보다 크다면, -1을 출력한다.

만약 답으로 가능한 수가 여러 개인 경우, 그중 아무거나 출력한다.

예제 입력

3
1 1 1
2 0 2
3 1 1

예제 출력

1
8
4

예제 입력 2

3
4 1 1
5 2 3
5 0 3

예제 출력 2

6
4
24

예제 입력 3

4
7 2 5
6 1 1
10 4 5
6 2 2

예제 출력 3

6
20
5
4

힌트