Let Y be an array of integers of size N.

Let G(x) be a set comprising of the size of all the subsets of the array Y whose sum is x.

Let F(G(x)) denote the number of unique elements in the set G(x).

Your task is to find the maximum value of F(G(x)) and the corresponding value x for the given array Y.

If multiple 'x' correspond to maximum F(G(x)), print the smallest one.

Input

The first line describes the number of test cases T.

The input contains several test cases, each one described in exactly two lines.

The first line contains an integer N indicating the number of elements in the array.

The second line contains N integers separated by single spaces, representing the elements of the array.

Output

For every test case, print two integers: maximum F(G(x)) and the minimum value of x corresponding to it.

Constraints

T <= 50
1 <= N <= 50
1 <= Y[i] <= 1000

Example

Input:
2
4
1 2 3 4
6
3 2 3 4 5 3

Output:
2 3
2 5

Explanation

For test Case 1

• G(1) : {1} and F(G(1)) : 1.
• G(2) : {1} and F(G(2)) : 1.
• G(3) : {1,2} and F(G(3)) : 2.
• G(4) : {1,2} and F(G(4)) : 2.
• G(5) : {2,2} and F(G(5)) : 1.
• G(6) : {2,3} and F(G(6)) : 2.
• G(7) : {2,3} and F(G(7)) : 2.
• G(8) : {3} and F(G(8)) : 1.
• G(9) : {3} and F(G(9)) : 1.
• G(10): {4} and F(G(10)) : 1.