Problem Statement

You are given an array of 'N' integers, and a positive integer 'K'. You need to determine if it is possible to divide the array into 'K' non-empty subsets such that the sum of elements of each subset is equal.

Note:

1. The array can have duplicate elements.

2. Each of the array elements must belong to exactly one of the 'K' subsets.

3. The elements chosen for a subset may not be contiguous in the array.

Input Format:

The first line of the input contains an integer 'T', denoting the number of test cases. The first line of each test case will contain an integer 'N', denoting the size of the input array. The second line of each test case will contain 'N' space-separated integers denoting the array elements. The third and last line of each input will contain the value 'K', which denotes the number of non-empty subsets you have to break the input array into.

Output Format:

For each test case, print a single line containing “True” if it is possible to divide the array into ‘K' equal sum subsets, “False” otherwise. The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10

1 <= N <= 15

0 <= NUMS[i] <= 10 ^ 3

1 <= K <= N

Where NUMS[i] denotes ith element of given array 'NUMS'.