Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/2/problems/D

Repovive

Rayan found an $N \times M$ grid of tiles. Each tile is either dark (0) or bright (1).

When you tap a tile at $(i, j)$ , it toggles along with all orthogonally adjacent tiles (up, down, left, right) that exist within the grid.

Find the minimum number of taps to make all tiles bright, or determine that it is impossible.

Input

The first line contains $t$ ( $1 \le t \le 20$ ), the number of test cases.

Each test case consists of:

The first line contains $N$ and $M$ ( $1 \le N, M \le 15$ ).
The next $N$ lines contain $M$ integers each (0 or 1).

The sum of $N \times M$ over all test cases does not exceed $500$ .

Output

For each test case, print the minimum number of taps, or $-1$ if impossible.

t \\[0.5em] \left. \begin{array}{l} N \quad M \\ G_{1,1} \quad G_{1,2} \quad \cdots \quad G_{1,M} \\ \vdots \\ G_{N,1} \quad G_{N,2} \quad \cdots \quad G_{N,M} \end{array} \right\} \times t

\begin{array}{l} T_1 \\ T_2 \\ \vdots \\ T_t \end{array}

Where each value is the minimum taps or $-1$ if unsolvable.

2D. Lights Out

Input

Output

Input

Output

Samples

Input

Output