We have to plan a path for a cleaning robot to clean a rectangular room floor of size N×M. 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 on to 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.

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 lines represent the arrangement of the room with following:

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

In the map the number of dirty squares is no more than 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 number of the test case. The next line is the minimum number of moves for the robot to change all dirty tiles into clean tiles. If the map includes dirty tiles that are inaccessible to the robot, your program will output -1.

Example

Input:
2
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