Polycarp is the project manager in the IT-company. Right now, he needs to choose developers for his team to start a new project. The company has n developers "on the bench" (i.e not involved in other projects). Polycarp assessed the skills of each of them: a_i (-10^4 ≤ a_i ≤ 10^4) — an integer characteristic of the i-th developer. This value can be either positive, zero or even negative (some developers cause distractions).

After Polycarp chooses a subset of developers for his team, the strength of the team will be determined by the sum of a_i values for all selected developers.

Polycarp fears that if he chooses a team in such a way that maximizes the sum of the characteristics of a_i, other managers may find this unacceptable. For this reason, he plans to create such a team that the sum of the a_i values for it is strictly less than the maximum possible value.

Help Polycarp choose any team that:

  * the sum of the characteristics a_i for all members of the selected team is strictly less than the maximum value that can be achieved by choosing the team in some other way 
  * and at the same time, the sum of the characteristics of a_i for all members of the selected team is the greatest possible. 



If, following the requirements above, you can select a team in several ways, then just find any of them. 

It's guaranteed that the sum of the characteristics in the desired subset is strictly positive (i.e. Polycarp can always choose a non-empty team).

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

Each test case begins with a line containing one integer n (2 ≤ n ≤ 10^5) — the number of developers "on the bench".

The second line of a test case contains a sequence of integers a_1, a_2, ..., a_n (-10^4 ≤ a_i ≤ 10^4) — the characteristics of the n developers. It is guaranteed that the characteristics are such that the sum of the characteristics in the answer is strictly positive.

It is guaranteed that the sum of n over all test cases in the input doesn't exceed 10^5.

Output

Print the answers for the given t test cases in the order that they appear in the input. In the first line of each answer, print a positive integer s — the sum of the characteristics in the desired subset. The second line should contain only the characters 0 and 1 and match the answer:

  * the character in the i-th position should be equal to 1 if the i-th developer belongs to the team; 
  * the character in the i-th position should be equal to 0 if the i-th developer does not belong to the team. 



If there are several answers, print any of them.

Example

Input


5
5
1 -1 1 -1 1
2
11 1
3
5 -3 4
3
5 3 -4
5
-1 0 3 -3 0


Output


2
11101
11
10
6
111
5
100
2
10100

Note

In the first test case, the maximum subset a_1, a_3, a_5 has a sum equal to 3, so Polycarp should choose a team with the maximum total sum which is less than 3.

In the second test case, the maximum subset a_1, a_2 has a sum equal to 12, so Polycarp should choose a team with the maximum total sum which is less than 12.

In the third test case, the maximum subset a_1, a_3 has a sum equal to 9.

In the fourth test case, the maximum subset a_1, a_2 has a sum equal to 8.

In the fifth test case, there are several subsets with a maximum sum equal to 3, so Polycarp should choose a team with a lower total sum.

Difficulty: UNKNOWN_DIFFICULTY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions: