ODDSUM

Problem

You are given an array consisting of N integers: ~A_1~, ~A_2~, ...~A_N~. You can select as many of these numbers as you want. The goal is to make the sum of the selected integers odd and maximize it.

Input Files:

The input files named oddsum.in are text files with the following structure: The first line of the input will contain a positive integer T: the number of queries. In each of the next T queries, the first line will contain a natural number N: the number of elements in the array. The second line will contain exactly N integers ~A_1~, ~A_2~, ...~A_N~ separated in pairs by a single space.

Output Files:

The output files named oddsum.out are text files with the following structure: The output should contain T lines. Each line should contain an integer, indicating the maximum possible odd sum of some selected numbers from the initial array for the corresponding query. If no selection of numbers can result in an odd sum, the line should contain the word "IMPOSSIBLE".

Constraints

• ~1~ ~\le~ ~T~ ~\le~ ~10~
• ~1~ ~\le~ ~N~ ~\le~ ~1.000.000~, and the sum of ~N~ over all queries will not exceed ~2.000.000~
• The absolute value of the sum of any subset of the array's (~A~) numbers will not exceed ~1.000.000.000~.

Example of Input - Output Files:

STDIN (oddsum.in)

3
4
-2 2 -3 1
3
2 -5 -3
5
2 4 6 8 4

STDOUT (oddsum.out)

3
-1
IMPOSSIBLE

Explanation of the Example

The example has three queries. In the first query, we can select the numbers ~2~ and ~1~ with a sum of ~3~. In the second query, the best we can do is to select the numbers ~2~ and ~-3~ with a sum of ~-1~. Finally, in the third query, no selection of numbers leads to a sum that is an odd number.

Notes

• For test cases worth 20%, of the total points, it will be: \(Ν\) ~\le~ ~20~.
• For test cases worth 50%, of the total points, it will be: \(Ν\) ~\le~ ~1000~. Maximum execution time: 1 sec.
  Maximum available memory: 64 MB.