Equal Sum Partition

You are given an array of integers. Your task is to determine whether the array can be partitioned into two subsets such that the sum of the elements in both subsets is equal.

If the total sum of the array is odd, then the partition is impossible. Otherwise, the goal is to find a subset that sums to \(\frac{\text{total sum}}{2}\). This can be achieved using dynamic programming.

Example:

Input: [1, 5, 11, 5]
Output: True
Input: [1, 2, 3, 5]
Output: False

</p>

inputFormat

The input begins with a single integer \(T\) denoting the number of test cases. Each test case consists of two lines:

• The first line is an integer \(N\), the number of elements in the array.
• The second line contains \(N\) space-separated integers representing the array elements.

The input is read from standard input (stdin).

outputFormat

For each test case, output True if it is possible to partition the array into two subsets with equal sum, otherwise output False. The answers for each test case should be printed on a new line to standard output (stdout).

## sample

2
4
1 5 11 5
5
1 2 3 5

True
False

</p>