Background

Special for beginners, ^_^

Description

8*8的国际象棋棋盘上的每个格子中都有一些金币，你放置八个皇后，要求这些皇后们不能互相攻击，皇后可以搬走所在格子中的金币，问皇后们最多能能搬走多少枚金币。

Format

Input

第一行一个正整数T（$\le4 \times 10^4$）表示测试例数量 . 后面T个8*8矩阵，表示对应格子的金币数量，每个格子不超过100枚金币。

Output

对于每个测试例，在一行中输该测试例的答案.

Samples

1
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

260

Limitation

1s, 1024KiB for each test case.