KRUSKAL - Kruskal

no tags 

A three-headed monkey was on his (theirs?) peaceful way from his dorm to the university. He decided to use the subway. But as soon as he descended into the station, he was stopped by a strange geek with a flashlight, saying strange words...

"I am a servant of the Secret Group Order, wielder of the flame of Primes. Your limited knowledge of partial derivatives will not avail you, flame of Riemann! You shall not pass! You can't beat Kruskal in his game!"

The three-headed monkey shook his head. The left one. But there was no way out. If he wanted to get to the university in time, he had to play.

(Many others in his situation would use the distract-and-run tactics to get past the evil Kruskal into the subway. However, this was not possible in this case : nobody will turn around upon hearing "Hey! Look behind you! A three-headed monkey!" when he already sees the monkey in front of him...)

So, what was the game about? It is a two-player game. At the beginning there are N (not necessarily equal) heaps of matches. On each turn, a player may only remove matches from one heap only, and he has to remove between 1 and K matches, inclusive. A player wins if after his move the size of some heap is a prime number. The three-headed monkey moves first.

Problem specification

You will be given several starting positions. For each of them, determine whether the three-headed monkey can win this game. You may assume that Kruskal (the monkey's opponent) plays optimally.

Input specification

The first line of the input file contains an integer T specifying the number of test cases.

Each test case looks as follows: on the first line there are the two integers N (1 <= N <= 200) and K (1 <= K <= 100), separated by a single space. N lines follow, one for each heap of matches. The i-th of these lines contains a single integer ai (3 <= ai < 232) giving the number of matches on the i-th heap.

Output specification

For each test case output one line. If the monkey can win the game, output the string "YES", otherwise output the string "NO".

Example

Input:
2

3 3
48
15
4

2 3
51
51

Output:
YES
NO
Note: a somewhat hard test has been removed.

hide comments
Piyush Kumar: 2016-06-23 14:59:59

What is the range of T?

:D: 2009-08-24 08:09:53

You mean prime at the start? I didn't solve this one yet, but treating the rules literally, only the end turn state matters. So monkey wins as long as there is other heap to take matches form.

Anton Lunyov: 2009-08-15 13:08:49

What I need to do if the number of matches in one of the heap is prime number?


Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:IPSC 2006