#PSYCHO3. Make Psycho

Make Psycho

Problem Statement:

The number N is called Psycho Number . Psycho Number is calculated as follows:

First, If we factorize N , then we have some prime and their power. Assume that, there are M powers. From M powers , you should count the number of even and odd powers. Then if the number of even power is strictly greater than odd power , then we call the number N is “Psycho Number”, otherwise the number N is call “Ordinary Number”.

As for example, if N = 67500 then prime factorization, 

67500 = 22 x 33 x 54

Count even powers and odd powers . This number have 2 even power(2,4) and 1 odd power ( 3 ). Since even power 2 (2,4) is greater than odd power 1 (3), so the number 67500 is a Psycho Number.

Now, Given an integer K, your task is to find whether it is possible to form a subset consisting of only psycho numbers that sum up to exactly K, or not.


Input:
The first line of the input contains an integer, T (1 ≤ T ≤ 2000) indicating the number of test cases. For each test case, two lines appear, the first one contains a number N (1 ≤ N ≤ 100), representing the length of the numbers . and K (1 ≤ K ≤ 105). The second line of each test case contains the sequence of integers p1, p2, ..., pn (0 ≤ pi ≤ 1100).  It's mixed with psycho number and ordinary number.
 

Output:
For each case print  “Yes” if possible to make K . otherwise “No”.

Sample Input/Output:

Sample Input

Sample Output

  3
  5 20
  4 5 12 20 16
  5 3
  3 5 9 2 7  
  3 24
  4 4 16

 Yes

 No

 Yes

 


Explanation
:
1st test case : psycho numbers :
4 and 16 .
possible number: 4, 16 and 20 (4+16).
k is 20 so you can make this number .
2nd test case : psycho numbers : only 9
k is 3 but it's not possible to make subset of psycho numbers which sum is equal to k .
3rd test case : psycho numbers : 4 4 16
possible number : 4 , 16 , 20(16+4) and 24 (16+4+4)
k is 24 so you can make this number .

Note : 0 and 1 is not a psycho number .
Psycho 1 : Psycho
Psycho 2 :
Psycho Function

Problem setter:   Shipu Ahamed, Dept. of CSE
Bangladesh University of Business and Technology (BUBT)