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)


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

hide comments
2014-05-13 17:12:21 [Lakshman]
@Shipu Ahamed What is the expected complexity? My initial AC solution TLE now.
But my new code complexity is O(sum*n) and still TLE.

Shipu : can you discuss these on SPOJ forums ?

Okay Done AC now.
But this is not a good idea to change the datasheet every time.However the datasheet have very strong cases.
any way Thanks.

Shipu : i m really sry and gd job........

Last edit: 2013-11-20 19:27:45
2014-05-13 17:12:21 যোবায়ের
problem statement needs refinement.

Shipu : thnx vaia.it's ok now

Last edit: 2013-11-19 09:20:48
2014-05-13 17:12:21 Shipu Ahamed
dataset update and rejudge .............. plz check everyone
2014-05-13 17:12:21 Jacob Plachta
The problem seems to never say what you're actually trying to do... You need to determine whether or not there exists a subset of the N numbers, consisting only of psycho numbers, which sum to K.

Shipu -> thnx


Last edit: 2013-11-18 08:51:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.