1.2 The Magical Odd Sum ðŸ”®

Score: 10pts

Time Limit: 5.00 sec

In the enchanted kingdom of Numera, Sir Marcauley challenges the villagers each year to find the Magical Odd Sumâ€”a mystical number that brings good fortune! The Quest: Villagers sum their array of positive integers. If the sum is odd, itâ€™s magical. If itâ€™s even, they subtract the smallest odd number to reveal the highest possible odd sum. If no odd sum can be obtained, they return 0. This quest ensures that every villager enjoys a year of prosperity and luck!

Task: Find out the maximum sum of the elements that is odd.

Task: Find out the maximum sum of the elements that is odd.

Constraints

1 â‰¤ T â‰¤ 10

1 â‰¤ n â‰¤ 10^5

1 â‰¤ ai â‰¤ 10^8

1 â‰¤ n â‰¤ 10^5

1 â‰¤ ai â‰¤ 10^8

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case:

The first line contains the integer n, the size of the array.

The second line contains n space-separated positive integers.

For each test case:

The first line contains the integer n, the size of the array.

The second line contains n space-separated positive integers.

Output Format

For each test case, print the answer in a new line.

Example 1

Input:

1

1

7

Output:

7

Explanation:

With only one odd number, the maximum odd sum is the number itself.

1

1

7

Output:

7

Explanation:

With only one odd number, the maximum odd sum is the number itself.