You have (n) coins with denominations (a_1, a_2, \ldots, a_n) and a natural number (k). You also have a bag, which is initially empty, where you can place coins. You need to perform exactly (k) actions. In each action, you take one coin from those you have left and put it in your bag. After that, you can no longer take that coin. At the same time, you have a cat that loves even numbers, so every time the sum of the denominations of the coins in your bag becomes even, your cat empties the bag, meaning it takes all the coins to a place known only to it, and the bag is empty again. Note that the bag is emptied every time the sum becomes even during the process of adding coins, not just at the very last moment. Let your score be the sum of the denominations of the coins in the bag. Your task is to perform (k) actions such that your final score is maximized. Find the answer for all (1 \le k \le n). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((1 \le n \le 2 \cdot 10^5)) — the number of coins you have. The second line of each test case contains (n) natural numbers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le 10^9)) — the denominations of the coins. It is guaranteed that the sum of (n) across all test cases does not exceed (2 \cdot 10^5). For each test case, output (n) numbers — the maximum possible score that can be achieved by performing exactly (k) actions for all (k) from (1) to (n). In the first set of input data, you have coins with denominations (1,1,1). (k=1): in this case, the sum of the denominations in the bag is (1), regardless of the chosen coin. The final score is also (1). (k=2): in this case, the sum of the denominations in the bag is initially (1), regardless of the choice