PSYCHO3 - 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.

Note: 0 and 1 are not psycho numbers.

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 a mix of psycho and ordinary numbers.

Output:

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

Example

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

Sample Output
Yes
No
Yes

Explanation

1st test case: psycho numbers: 4 and 16. Possible numbers: 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 with sum equal to k.

3rd test case: psycho numbers: 4 4 16. Possible numbers: 4, 16, 20 (16 + 4) and 24 (16 + 4 + 4). k is 24 so you can make this number.

Psycho 1: Psycho
Psycho 2: Psycho Function

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


hide comments
vaibhav2303: 2018-12-24 11:13:32

Its amazing what a bitset can do!

:.Mohib.:: 2015-06-27 11:38:25

O(N^2)+O(sqrt(P)*N) TLE :(....any hint plz...

kaushal yadav: 2014-11-01 17:14:32

finally green light after lots of TLEs.:)

Garvit Choudhary: 2014-09-02 11:38:51

Can u pl tell me why am i getting WA ?
ID: 12286842
Edit: Sorry very silly mistake. GOT AC

Last edit: 2014-09-02 11:41:18
GURVINDER SINGH: 2014-06-03 19:46:15

AC :) just one clever optimisation needed
0.25 sec

Shipu Ahamed: 2014-05-13 17:12:21

i don't understand why this one is turorial........... this is not a tutorial problem........... it's better EB member Hidden the problem ........ and can you please explain Francky sir why this one is tutorial...
--ans(Francky)--> It is tutorial problem as a mix of tutorial problem PSYCHO (and even easier), and another easy common task. Please stop counter EB actions.

Last edit: 2014-05-13 19:15:57
Rishav Goyal: 2014-05-13 17:12:21

@as Jacob Said, i din actually like this problem dataset. Bcz technically the worst solution is (2000*10^5*100). then how come it fits in 0.5 sec anyhow.
same problem with the "Psycho" . Either u set ur testcases or constraints so the problem data atleast make some sense technically.
shipu -> discuss these on SPOJ forums.

Last edit: 2014-04-20 14:38:26
Bhavik: 2014-05-13 17:12:21

finally.......the green light....

P_Quantum: 2014-05-13 17:12:21

Nice prblm.. :)

anurag garg: 2014-05-13 17:12:21

Edit:AC
hell lot of optimization needed to get AC..
very good problem shipu sir

Last edit: 2014-01-08 16:44:13

Added by:Shipu Ahamed
Date:2013-11-17
Time limit:0.5s
Source limit:9000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64