Shops

A fair site is an N by 5 grid. Each cell has a profit estimate. You may rent any set of cells, but no two rented cells may be side-adjacent (up, down, left, or right). Find the maximum total profit.

The first line has T test cases. Each test case starts with N, followed by five lines of N nonnegative profits.

For each test case, print the maximum total profit from a non-adjacent selection.