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. 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. 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. Output For each test case, the output should contain the minimum number of movements of the corresponding case. Sample Input 5 53 54578 36329 75241
2/2 91 759456785 22 22 22 66 777777 772777 777777 777727 727777 777777 77 1811181 1118811 1881111 8111111 1188181 1881181 1111111 Sample Output 11 7 3 11 24