Coin Row

There is a row of n coins whose values are some positive integers, c1, c2, …, cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two adjacent coins can be selected.

The first line of input will be a positive integer, n, indicating the number of coin rows that follow. Following the positive integer will be n coin rows, one per line. Each coin row will be a list of positive integers separated by one or more blanks, and there will be at most 20 coins in any one row.

For each coin row print, on a separate line, the maximum amount of money you can pick up subject to the constraint that no two adjacent coins are selected. The output should be an unformatted positive integer.