상점

N열 5행 격자의 각 칸에 예상 수익이 있다. 인접한 두 칸(상하좌우)을 동시에 임대할 수 없을 때, 임대 수익 합의 최댓값을 구하라.

첫 줄에 테스트 수 T. 각 테스트는 N, 이어서 5행의 N개 수익 값으로 주어진다.

각 테스트마다 인접 칸을 모두 피했을 때 얻을 수 있는 최대 총 수익을 출력한다.