提示: 欢迎访问OurACM平台。
Problem 1467 Pick Up Points

Accept: 210    Submit: 753
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Recently loy are very interested in playing a funny game. There is a board of n*m grid. Each grid has one point or not. If two adjacency grids both have one point, someone can pick them up, and then these two grids have no point. The two grids are adjacency only if the Manhattan distence between them is exactly 1.

The purpose of the game is to gain as many points as possible.

Input

The first line is an interger T, means the number of test cases. Each test case begins with two interger n,m (1 <= n,m <= 100), means the size of the board is n*m. Next n line, each line has m intergers which is 1 or 0, means the grid has one point or not.

Output

Output the maximum point loy can get.

Sample Input

2 3 4 0 1 0 1 0 1 1 0 1 1 1 1 2 2 1 0 0 1

Sample Output

6 0

Source

LOY

Submit  Back  Status  Discuss