Context

Spring has arrived and our friend Pepito has fallen in love. But he is not sure if she also loves him, so he decides to ask the daisies. He takes a daisy and alternately speaks the phrases "She loves me" and "She loves me not", while picking one petal off the flower for each phrase. The phrase corresponding to the last petal tells him whether his love is reciprocated or not.

We want to help Pepito to always obtain the answer "She loves me". Therefore, we will make sure that all the daisies have an odd number of petals, by picking one petal off the flowers with an even number.

The Problem

We have a rectangular field of daisies, whose width is W and height H. There is a daisy in each position of this field (w, h), with w= 1, 2, ..., W, and h= 1, 2, ..., H. We have patiently counted the number of petals of each daisy, P[w, h].

Starting from the upper-left corner of the field --i.e., from position (1, 1)-- you have to pass through all positions of daisies with an even number of petals. If your current position is (w, h), you can only do three movements: go down (h+1), go left (w-1) and go right (w+1).

Your task is to compute the minimum number of movements necessary to pass through all positions with an even number of petals.

A sample case with W = 5 and H = 3. The solution is 11. This sample corresponds to the first case in the sample input.

The Input

The first line of the input contains an integer indicating the number of test cases.

For each test case, the first line contains two integers, W and H, separated by a blank space. Then, there are H lines. Each line consists of W digits (between 1 and 9) indicating the number of petals of the corresponding daisy.

The Output

For each test case, the output should contain the minimum number of movements of the corresponding case.

Sample Input

5
5 3
54578
36329
75241
9 1
759456785
2 2
22
22
6 6
777777
772777
777777
777727
727777
777777
7 7
1811181
1118811
1881111
8111111
1188181
1881181
1111111

Sample Output

11
7
3
11
24

OMP'09
Facultad de Informatica
Universidad de Murcia (SPAIN)