시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 64 MB 83 14 9 19.149%

문제

준형이와 민형이가 수열 게임을 한다. 게임을 시작하기에 앞서, 민형이는 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을 출력한다.

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

예제 입력 1

3
1 1 1
2 0 2
3 1 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
W3sicHJvYmxlbV9pZCI6IjExOTU4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTg5XHViY2Y1XHVkNTVjIFx1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjOTAwXHVkNjE1XHVjNzc0XHVjNjQwIFx1YmJmY1x1ZDYxNVx1Yzc3NFx1YWMwMCBcdWMyMThcdWM1ZjQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMFx1YzVkMCBcdWM1NWVcdWMxMWMsIFx1YmJmY1x1ZDYxNVx1Yzc3NFx1YjI5NCBLLCBMLCBNIDNcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YmY1MVx1YjI5NFx1YjJlNC4gXHViYmZjXHVkNjE1XHVjNzc0XHVhYzAwIFx1YzIxOFx1Yjk3YyBcdWJmNTFcdWM1NThcdWIyZTRcdWJhNzQsIFx1YzkwMFx1ZDYxNVx1Yzc3NFx1YjI5NCBLXHVhYzFjXHVjNzU4IFx1YzVmMFx1YzE4ZFx1ZDU1YyBcdWM3OTBcdWM1ZjBcdWMyMThcdWI5N2MgXHViOWQwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmZjXHVkNjE1XHVjNzc0XHViMjk0IFx1YzkwMFx1ZDYxNVx1Yzc3NFx1Yzc1OCBcdWM1NTRcdWMwYjAgXHVjMmU0XHViODI1XHVjNzQ0IFx1ZDBhNFx1YzZiMFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHViOGYwXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOTRcdWFjMDBcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWI4ZjBcdWM1ZDAgXHViNTMwXHViOTc0XHViYTc0LCZuYnNwO1x1YzkwMFx1ZDYxNVx1Yzc3NFx1YWMwMCBLXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWI5ZDBcdWQ1NThcdWJhNzQmbmJzcDtcdWFkZjggXHVjOTExXHVjNWQwXHVjMTFjICYjMzk7XHVkNTg5XHViY2Y1XHVkNTVjIFx1YzIxOCYjMzk7XHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBMXHVhYzFjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU4OVx1YmNmNVx1ZDU1YyBcdWMyMThcdWIyOTQgXHVjNTQ0XHViNzk4IFx1YjQ1MCBcdWM4NzBcdWFjNzQgXHVjOTExIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NDQgXHViOWNjXHVjODcxXHVjMmRjXHVkMGE0XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjMjE4XHVhYzAwIE0gXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3OCBcdWFjYmRcdWM2YjA8XC9saT5cclxuXHQ8bGk+XHVjMjE4XHVhYzAwIFx1YzE4Y1x1YzIxOChcdWM1N2RcdWMyMThcdWFjMDAgXHVjODE1XHVkNjU1XHVkNzg4IDJcdWFjMWNcdWM3NzggXHVjMjE4KVx1Yzc3OCBcdWFjYmRcdWM2YjA8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM5MDBcdWQ2MTVcdWM3NzRcdWIyOTQgXHViYmZjXHVkNjE1XHVjNzc0XHVjNzU4IFx1YzljOFx1YmIzOFx1YzVkMCBcdWJlNjBcdWI5NzggXHViMzAwXHViMmY1XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YmFiMFx1Yjc5OCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjJmNVx1Yzc0NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiZmNcdWQ2MTVcdWM3NzRcdWM3NTggXHVjOWM4XHViYjM4XHVjNWQwIFx1YjJmNVx1Yzc0NCBcdWQ1NzRcdWM4ZmNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFEmbmJzcDsoMSAmbGU7IFEgJmxlOyAxMDAgMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IEssIEwsIE1cdWM3NTggXHVhYzEyXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBLLCBNICZsZTsgMTUwLCAwICZsZTsgTCAmbGU7IEspPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjOTAwXHVkNjE1XHVjNzc0XHVhYzAwIFx1YjlkMFx1ZDU3NFx1YzU3YyBcdWQ1NjAgS1x1YWMxY1x1Yzc1OCBcdWMyMThcdWI0ZTQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YjJmNVx1Yzc3NCBcdWM1YzZcdWFjNzBcdWIwOTggMTAgMDAwIDAwMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWIyZTRcdWJhNzQsIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1YjJmNVx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMjE4XHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwLCBcdWFkZjhcdWM5MTEgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTk1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBST1NUSSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYW5kIGhpcyBvbGRlciBicm90aGVyIFNsYXZrbyBhcmUgcGxheWluZyBhIGdhbWUuIEF0IHRoZSBiZWdpbm5pbmcgb2YgdGhlIGdhbWUsIHRoZXkgcGljayB0aHJlZSBudW1iZXJzIEssIEwsIE0uIEluIHRoZSBmaXJzdCBhbmQgb25seSBzdGVwIG9mIHRoZSBnYW1lLCBlYWNoIG9mIHRoZW0gcGlja3MgdGhlaXIgb3duIEsgY29uc2VjdXRpdmUgaW50ZWdlcnMuPFwvcD5cclxuXHJcbjxwPlNsYXZrbyBhbHdheXMgcGlja3MgdGhlIGZpcnN0IEsgaW50ZWdlcnMgKG51bWJlcnMgMSwgMiwgLi4uLCBLKS4gTWlya28gaGFzIGEgc3BlY2lhbCBkZW1hbmQgJm5kYXNoOyBoZSB3YW50cyB0byBjaG9vc2UgaGlzIG51bWJlcnMgaW4gYSB3YXkgdGhhdCB0aGVyZSBhcmUgZXhhY3RseSBMIGhhcHB5IG51bWJlcnMgYW1vbmcgdGhlbS4gSGUgY29uc2lkZXJzIGEgbnVtYmVyIGhhcHB5IGlmIGl0IG1lZXRzIGF0IGxlYXN0IG9uZSBvZiB0aGUgZm9sbG93aW5nIHJlcXVpcmVtZW50czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgbnVtYmVyIGlzIHNtYWxsZXIgdGhhbiBvciBlcXVhbCB0byBNPFwvbGk+XHJcblx0PGxpPnRoZSBudW1iZXIgaXMgcHJpbWU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5PdXQgb2YgcmVzcGVjdCB0byBoaXMgb2xkZXIgYnJvdGhlciwgTCB3aWxsIGJlIHNtYWxsZXIgdGhhbiBvciBlcXVhbCB0byB0aGUgdG90YWwgbnVtYmVyIG9mIGhhcHB5IG51bWJlcnMgaW4gU2xhdmtvJnJzcXVvO3MgYXJyYXkgb2YgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+VGhleSB3aWxsIHBsYXkgYSB0b3RhbCBvZiBRIGdhbWVzIHdpdGggZGlmZmVyZW50IHZhbHVlcyBLLCBMLCBNLiBGb3IgZWFjaCBnYW1lLCBoZWxwIE1pcmtvIGZpbmQgYW4gYXJyYXkgdGhhdCBtZWV0cyBoaXMgZGVtYW5kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgUSAoMSAmbGU7IFEgJmxlOyAxMDAgMDAwKS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIFEgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsIHRoZSBpIHRoIGxpbmUgY29udGFpbmluZyBpbnRlZ2VycyBLPHN1Yj5pPFwvc3ViPiwgTDxzdWI+aTxcL3N1Yj4sIE08c3ViPmk8XC9zdWI+ICgxICZsZTsgSzxzdWI+aTxcL3N1Yj4sIE08c3ViPmk8XC9zdWI+ICZsZTsgMTUwLCAwICZsZTsgTDxzdWI+aTxcL3N1Yj4gJmxlOyBLPHN1Yj5pPFwvc3ViPikgdGhhdCBkZXRlcm1pbmUgdGhlIHZhbHVlcyBLLCBMLCBNIHRoYXQgd2lsbCBiZSB1c2VkIGluIHRoZSBpIHRoIGdhbWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IFEgbGluZXMsIHRoZSBpIHRoIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyLCB0aGUgaW5pdGlhbCBudW1iZXIgb2YgTWlya28mcnNxdW87cyBhcnJheSBpbiB0aGUgaSB0aCBnYW1lLiBJZiBhbiBhcnJheSB3aXRoIHRoZSBpbml0aWFsIG51bWJlciBiZWluZyBzbWFsbGVyIHRoYW4gb3IgZXF1YWwgdG8gMTAgMDAwIDAwMCBkb2VzIG5vdCBleGlzdCwgb3V0cHV0ICZtaW51czsxLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgcG9zc2libGUgc29sdXRpb25zLCBvdXRwdXQgYW55LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==