Given an integer sequence which contains N positive integers, please output whether the sequence can be partitioned into K equal sum subsets. For example,
Input sequence = 2, 1, 3, 9, 5, 2, 1, 5, K = 2
We can partition it into two equal sum subsets as the following shows:
Subset 1: 1, 1, 3, 9 , sum = 14
Subset 2: 2, 2, 5, 5 , sum = 14
Therefore, we should output 'True' as the answer.
Notice: For each testcase, you will get q sequence to deal with.
First line contains an integer q which denotes the number of the sequences. (1 ≤ q ≤ 20)
The following 2×q lines denote all the sequences in the testcase.
For each sequence,
first line contains two integers N, K which denote the length of the sequence and partition number. (2 ≤ N ≤ 10, 2 ≤ K ≤ 5)
second line contains N integers seperated by blanks which denote the input sequence.
(1 ≤ each number in the given sequence < 30)
Output contains q lines.
For each line, output the answer of the corresponding sequence ended with a newline.