PRMHT - PRIME HEIGHT

Vedika, being taller than most of the guys of her class, constantly teases them. One day, Piyush got irritated with her habit and asked her a question.

"There are n boys in the class. The height of few boys is prime. You have to find a height h so that there are at least k boys who have a height x where x is a prime number and x is less than or equal to h. What is the minimum possible value of h?"

If Vedika fails to answer this question, she would have to stop teasing others and she is in no mood to do that. Can you help her?

If there is no such possible value the answer would be -1.

Input

First line will contain a single integer t (number of test cases), 2*t lines follows.

For every pair of lines following:

First line will contain two space separated integers n and k.

Second line will contain n space separated integers Hi (heights of boys) 1<=i<=n.

Output

Value of h if exists else print -1 (all in separate line).

Example

Input:
2
5 7
1 2 3 4 5
3 2
2 3 9

Output:
-1
5

Added by:realflash
Date:2017-02-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2022-06-25 21:00:55
Why I can't submit this problem?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.