행복한 수

시간 제한0.5초메모리 제한64 MB

요약

M 이하이거나 소수인 수가 정확히 L개 들어 있는 길이 K인 연속 구간 중 가장 작은 시작값을 구합니다.

난이도: 보통10점 중 5점
유형: 정수론, 누적 합, 슬라이딩 윈도우
정답자: 아직 제출이 없습니다

문제

준형이와 민형이가 수열 게임을 한다. 게임을 시작하기 전에 민형이가 세 수 $K$ , $L$ , $M$ 을 고르면, 준형이는 연속한 자연수 $K$ 개를 말해야 한다.

민형이는 준형이의 암산 실력을 키우려고 규칙을 하나 더 붙였다. 준형이가 말한 $K$ 개의 수 중에서 행복한 수가 정확히 $L$ 개여야 한다. 행복한 수는 다음 두 조건 중 하나 이상을 만족하는 수이다.

$M$ 이하의 자연수이다.
소수(약수가 정확히 2개인 수)이다.

준형이는 암산이 느려서 몰래 컴퓨터로 답을 구하려고 한다. 민형이의 질문에 답하는 프로그램을 작성하여라.

입력

첫째 줄에 테스트 케이스의 수 $Q$ ( $1 \le Q \le 100\,000$ )가 주어진다.

다음 $Q$ 개의 줄에 각각 $K$ , $L$ , $M$ 이 주어진다. ( $1 \le K, M \le 150$ , $0 \le L \le K$ )

출력

각 테스트 케이스마다 준형이가 말하는 $K$ 개의 수 중 가장 작은 수, 곧 연속한 자연수 $K$ 개의 시작 값을 한 줄에 출력한다. 조건을 만족하는 시작 값이 여러 개이면 그중 가장 작은 값을 출력한다. 조건을 만족하는 시작 값이 없거나 가장 작은 시작 값이 10,000,000보다 크면 -1을 출력한다.

예제3

예제 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
```
예상 출력
```
6
4
24
```
예제 3
입력
```
4
7 2 5
6 1 1
10 4 5
6 2 2
```
예상 출력
```
6
20
5
4
```