1.2 The Magical Odd Sum 🔮
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.
Constraints
1 ≤ T ≤ 10
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.
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.
Log In to solve the Question