정사각형 쿠키 하나가 같은 크기의 작은 정사각형 칸으로 나뉘어 있다. 각 칸에는 \(0\)부터 \(9\)까지의 정수 하나가 적혀 있다.

쿠키 조각의 한 변이 두 칸 이상이라면 다음 과정으로 조각을 자른다.

1. 조각에 포함된 모든 칸의 수를 더하고, 그 합을 \(4\)로 나눈 나머지를 구한다.
2. 조각을 크기가 같은 네 개의 정사각형으로 나눈다.
3. 나머지에 따라 다음 표에 해당하는 조각 하나를 버린다.

버리지 않은 세 조각에도 각각 같은 과정을 적용한다. 한 변의 길이가 \(1\)인 조각은 더 자르지 않는다.

모든 절단이 끝난 뒤 남은 칸에 적힌 수의 합을 구하여라.

입력

첫째 줄에 쿠키의 개수 \(T\)가 주어진다.

각 쿠키에 대하여 첫째 줄에 쿠키의 한 변의 길이 \(N\)이 주어진다. 다음 \(N\)개의 줄에는 각 칸의 수가 공백 없이 한 줄에 하나씩 주어진다.

출력

각 쿠키에 대해 모든 절단이 끝난 뒤 남은 칸에 적힌 수의 합을 한 줄에 하나씩 출력한다.

제한

• \(1 \le T \le 10\)
• \(1 \le N \le 1,024\)
• \(N\)은 \(2\)의 거듭제곱이다.
• 각 칸에 적힌 수는 \(0\) 이상 \(9\) 이하이다.

예제 입력 1

2
1
7
2
12
34

예제 출력 1

7
7

두 번째 쿠키에 적힌 수의 합은 \(10\)이고, 이를 \(4\)로 나눈 나머지는 \(2\)이다. 따라서 왼쪽 아래 칸을 버리며, 남은 세 칸의 합은 \(1+2+4=7\)이다.