Untitled

Có 1 trò chơi với dãy gồm N số như sau:

Mỗi bước đi bạn phải chia mảng thành 2 phần không rỗng sao cho tổng các phần tử bên trái bằng tổng phần tử bên phải. Nếu chia được bạn sẽ được 1 điểm, nếu không chia được trò chơi kết thúc.

Sau mỗi lần chia thành công, bạn phải bỏ 1 trong 2 phần đã chia và tiếp tục trò chơi với phần còn lại.

Cho 1 dãy, hỏi số điểm nhiều nhất mà bạn có thể thu được là bao nhiêu?

Input

Dòng đầu tiên là số lượng test case T (T <= 20).

Dòng đầu tiên của mỗi test case là N (N <= 20,000) là số lượng phần tử của dãy. Dòng tiếp theo là N phần tử của dãy đó.

 

Output

Mỗi test case in ra số điểm nhiều nhất mà có thể thu được

 

Sample

Input

3

3

3 3 3

4



2 2 2 2

7

4 1 0 1 1 0 1

Output

0

2

3

We have to plan a path for a cleaning robot to clean a rectangular room floor of size NxM. The room floor paved with square tiles whose size fits the cleaning robot (1 × 1). There are clean tiles and dirty tiles, and the robot can change a dirty tile to a clean tile by visiting the tile. Also there may be some obstacles (furniture) whose size fits a tile in the room. If there is an obstacle on a tile, the robot cannot visit it. The robot moves to an adjacent tile with one move. The tile onto which the robot moves must be one of four tiles (i.e., east, west, north or south) adjacent to the tile where the robot is present. The robot may visit a tile twice or more.

Your task is to write a program which computes the minimum number of moves for the robot to change all dirty tiles to clean tiles, if ever possible.

Time limit: 1s (C/C++), 2s (Java)

Submit limit: 10 times

Example:

The following is a room of size 5x7, with 3 dirty tiles, and 0 furniture. The answer for this case is 8.




Input

The input consists of multiple maps, the first line is the number of test case T (T < = 50).

Each test case begins with N and M representing the size of the room. ( 5 =< N, M <= 100)

The next N line representing the arrangement of the room with following describe:

0 : a clean tile
1 : a dirty tile
2 : a piece of furniture (obstacle)
3 : the robot (initial position)

In the map the number of dirty tiles does not exceed 10 and there is only one robot.

Output

Print each test case on two lines, the first line of each test case is "Case #x", where x is the test case number. The next line is the minimum number of moves for the robot to change all dirty tiles to clean tiles. If the map includes dirty tiles which the robot cannot reach, your program should output -1.

Sample

Input

5

5 7

0 0 0 0 0 0 0

0 3 0 0 0 1 0

0 0 0 0 0 0 0

0 1 0 0 0 1 0

0 0 0 0 0 0 0

5 15

0 0 0 0 2 0 2 0 0 0 0 1 2 0 1

0 0 0 1 0 2 0 2 2 0 1 2 0 0 0

2 1 0 2 0 1 0 2 0 0 0 0 0 0 0

0 0 0 1 0 2 0 0 1 2 0 0 2 0 0

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

...............

Output

Case #1

8

Case #2

38

Case #3

37

Case #4

-1

Case #5

49


You are given 28 different types of domino, each domino has size of 1x2 with 2 numbers on it as follow



And a board of size 7x8, your task is cover the board with above dominos such that a domino can only be placed on two adjacent squares on board if the numbers of the squares and of domino are equal.

How many different way to cover the board?

For example if the board are given as below, there are 18 way to cover it, one of them is as below.







Input

The first line is the number of test case T (T < = 50).

Each test case will be given on 7 lines, each line have 8 numbers separate by a space is the board for the test case. It have a empty line between 2 test cases.

Output

Print each test case on two lines, the first line is "Case #x", where x is the test case number, the next line is the numbers of different way to cover the board.

Sample

Input

2

6 1 6 5 3 2 5 0

6 6 0 1 6 0 4 4

2 2 3 6 5 5 1 5

1 2 0 4 4 3 4 2

5 2 1 1 4 1 3 0

3 3 0 2 3 5 2 6

1 3 4 6 4 5 0 0

 

6 6 6 0 1 4 6 3

2 5 3 3 3 5 5 4

0 0 4 3 3 1 2 4

4 4 2 0 5 5 3 0

0 1 2 2 6 1 2 1

4 6 2 6 5 6 0 4

5 0 5 1 1 1 2 3

...

 

Output

 

Case #1

32

Case #2

24