#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;
const int MAX_W = 9;
typedef pair<int,int> ii;


int h,w;
int field[10][10],indice[10][10];
int dp[2][1<<((MAX_W+1)*2)];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

inline bool isValid(int x,int y) { return 0 <= x && x < w && 0 <= y && y < h; }

#define SET(bitmask,index,value) ( bitmask = ( ( bitmask & ~(1<<(2*index)) & ~(1<<(2*index+1)) ) | ( value << (index*2) ) ) )
#define GET(bitmask,x) ( ( ( bitmask >> ( 2 * x ) ) & 1 ) | ( ( ( bitmask >> (2*x+1) ) & 1) << 1 ) )
#define FIX(bitmask) ((bitmask<<2)&((1<<(2*(w+1)))-1))
#define STAR ( field[y][x] == 2 || field[y][x] == 3 )
#define update(x,v) ( ( x == -1 ) ? ( x = v ) : ( x = min(x,v) ) )


void compute(){

  vector<int> state;
  rep(bitmask,(1<<((w+1)*2))) {
    bool success = true;
    for(int i=0;i<(w+1)*2;i+=2) if( ( ( bitmask >> i ) & 1 ) && ( ( bitmask >> (i+1) ) & 1 ) ) { success = false; break; }
    if( success ) state.push_back(bitmask);
  }
  memset(dp,-1,sizeof(dp));

  int _size = state.size();
  bool initter = true, phase = false;
  int mini = IINF;
  int encounter = 0;
  rep(y,h){
    rep(x,w){

      if( field[y][x] == 2 || field[y][x] == 3 ) ++encounter;
      if( initter ) dp[phase][0] = 0;

      rep(i,_size){
        int bitmask = state[i];

        if( dp[phase][bitmask] == -1 ) continue;
        if( dp[phase][bitmask] >= mini ) continue;

        // ?????????
        if( field[y][x] == 1 ) {
          int nbitmask = bitmask;
          SET(nbitmask,x,0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]);
          continue;
        }

        int nbitmask;
        // 0 0
        if( !( ( GET(bitmask,x) == 0 ) && ( GET(bitmask,(x+1)) == 0 ) ) ) goto Label1;
        if( STAR ) {
          // x 0
          if( y+1 < h && field[y+1][x] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,((field[y][x]==3)+1));
            if( x == w-1 ) nbitmask = FIX(nbitmask);
          
            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
          // 0 x
          if( x+1 < w && field[y][x+1] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,(x+1),((field[y][x]==3)+1));

            if( x == w-1 ) nbitmask = FIX(nbitmask);

            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
        } else {
          // x x
          if( x+1 < w && y+1 < h && field[y][x+1] != 1 && field[y+1][x] != 1 ) {
            REP(color,1,3){
              nbitmask = bitmask;
              SET(nbitmask,x,color);
              SET(nbitmask,(x+1),color);
              if( x == w-1 ) nbitmask = FIX(nbitmask);
              update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
            }
          }
          // 0 0
          nbitmask = bitmask;
          SET(nbitmask,x,0);
          SET(nbitmask,(x+1),0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]);
        }

        continue;
      Label1:;
        // x 0
        // 0 x
        int color;
        if( !( ( GET(bitmask,x) && ( GET(bitmask,(x+1)) == 0 ) ) || ( GET(bitmask,(x+1)) && ( GET(bitmask,x) == 0 ) ) ) ) goto Label2;
        color = GET(bitmask,x) | GET(bitmask,(x+1));
        if( STAR ) {
          // 0 0
          if( ((color==1)?2:3) == field[y][x] ) {
            nbitmask = bitmask;
            SET(nbitmask,x,0);
            SET(nbitmask,(x+1),0);
            if( x == w-1 ) nbitmask = FIX(nbitmask);
            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
        } else {
          // x 0
          if( y+1 < h && field[y+1][x] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,color);
            SET(nbitmask,(x+1),0);
            if( x == w-1 ) nbitmask = FIX(nbitmask);


            update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
          }
          
          // 0 x
          if( x+1 < w && field[y][x+1] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,0);
            SET(nbitmask,(x+1),color);

            if( x == w-1 ) nbitmask = FIX(nbitmask);
            update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
          }
        }
        continue;
      Label2:;
        // x x
        if( !( GET(bitmask,x) && GET(bitmask,(x+1)) ) ) goto Label3;
        if( GET(bitmask,x) != GET(bitmask,(x+1)) ) goto Label3;

        color = GET(bitmask,x);
        
        // 0 0
        if( !STAR ) {
          nbitmask = bitmask;
          SET(nbitmask,x,0);
          SET(nbitmask,(x+1),0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
        }
      Label3:;

      }
      if( field[y][x] == 2 || field[y][x] == 3 ) initter = false;
      rep(i,_size) dp[phase][state[i]] = -1;
      if( encounter >= 4 && dp[!phase][0] != -1 ) {
        mini = min(mini,dp[!phase][0]);
      }
      phase = !phase;
    }
  }
  if( dp[phase][0] != -1 ) mini = min(mini,dp[phase][0]);
  if( mini != IINF ) printf("%d\n",mini-2);
  else puts("0");
}

int main(){
  while( scanf("%d %d",&h,&w), h|w ){
    rep(i,h) rep(j,w) scanf("%d",&field[i][j]);
    compute();
  }
  return 0;
}
### Prompt

Please create a solution in CPP to the following problem:

There is a rectangular area containing n × m cells. Two cells are marked with "2", and another two with "3". Some cells are occupied by obstacles. You should connect the two "2"s and also the two "3"s with non-intersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles.

Lines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length 1.

Fig. 6(a) shows an example setting. Fig. 6(b) shows two lines satisfying the constraints above with minimum total length 18.


<image>

Figure 6: An example setting and its solution



Input

The input consists of multiple datasets, each in the following format.


n m
row1
...
rown


n is the number of rows which satisfies 2 ≤ n ≤ 9. m is the number of columns which satisfies 2 ≤ m ≤ 9. Each rowi is a sequence of m digits separated by a space. The digits mean the following.

0: Empty

1: Occupied by an obstacle

2: Marked with "2"

3: Marked with "3"

The end of the input is indicated with a line containing two zeros separated by a space.

Output

For each dataset, one line containing the minimum total length of the two lines should be output. If there is no pair of lines satisfying the requirement, answer "0" instead. No other characters should be contained in the output.

Example

Input

5 5
0 0 0 0 0
0 0 0 3 0
2 0 2 0 0
1 0 1 1 1
0 0 0 0 3
2 3
2 2 0
0 3 3
6 5
2 0 0 0 0
0 3 0 0 0
0 0 0 0 0
1 1 1 0 0
0 0 0 0 0
0 0 2 3 0
5 9
0 0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0
0 2 0 0 0 0 0 2 0
0 0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0 0
9 9
3 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 3
9 9
0 0 0 1 0 0 0 0 0
0 2 0 1 0 0 0 0 3
0 0 0 1 0 0 0 0 2
0 0 0 1 0 0 0 0 3
0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
9 9
0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 3 2
0 0


Output

18
2
17
12
0
52
43

### Response

```cpp
#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;
const int MAX_W = 9;
typedef pair<int,int> ii;


int h,w;
int field[10][10],indice[10][10];
int dp[2][1<<((MAX_W+1)*2)];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

inline bool isValid(int x,int y) { return 0 <= x && x < w && 0 <= y && y < h; }

#define SET(bitmask,index,value) ( bitmask = ( ( bitmask & ~(1<<(2*index)) & ~(1<<(2*index+1)) ) | ( value << (index*2) ) ) )
#define GET(bitmask,x) ( ( ( bitmask >> ( 2 * x ) ) & 1 ) | ( ( ( bitmask >> (2*x+1) ) & 1) << 1 ) )
#define FIX(bitmask) ((bitmask<<2)&((1<<(2*(w+1)))-1))
#define STAR ( field[y][x] == 2 || field[y][x] == 3 )
#define update(x,v) ( ( x == -1 ) ? ( x = v ) : ( x = min(x,v) ) )


void compute(){

  vector<int> state;
  rep(bitmask,(1<<((w+1)*2))) {
    bool success = true;
    for(int i=0;i<(w+1)*2;i+=2) if( ( ( bitmask >> i ) & 1 ) && ( ( bitmask >> (i+1) ) & 1 ) ) { success = false; break; }
    if( success ) state.push_back(bitmask);
  }
  memset(dp,-1,sizeof(dp));

  int _size = state.size();
  bool initter = true, phase = false;
  int mini = IINF;
  int encounter = 0;
  rep(y,h){
    rep(x,w){

      if( field[y][x] == 2 || field[y][x] == 3 ) ++encounter;
      if( initter ) dp[phase][0] = 0;

      rep(i,_size){
        int bitmask = state[i];

        if( dp[phase][bitmask] == -1 ) continue;
        if( dp[phase][bitmask] >= mini ) continue;

        // ?????????
        if( field[y][x] == 1 ) {
          int nbitmask = bitmask;
          SET(nbitmask,x,0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]);
          continue;
        }

        int nbitmask;
        // 0 0
        if( !( ( GET(bitmask,x) == 0 ) && ( GET(bitmask,(x+1)) == 0 ) ) ) goto Label1;
        if( STAR ) {
          // x 0
          if( y+1 < h && field[y+1][x] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,((field[y][x]==3)+1));
            if( x == w-1 ) nbitmask = FIX(nbitmask);
          
            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
          // 0 x
          if( x+1 < w && field[y][x+1] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,(x+1),((field[y][x]==3)+1));

            if( x == w-1 ) nbitmask = FIX(nbitmask);

            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
        } else {
          // x x
          if( x+1 < w && y+1 < h && field[y][x+1] != 1 && field[y+1][x] != 1 ) {
            REP(color,1,3){
              nbitmask = bitmask;
              SET(nbitmask,x,color);
              SET(nbitmask,(x+1),color);
              if( x == w-1 ) nbitmask = FIX(nbitmask);
              update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
            }
          }
          // 0 0
          nbitmask = bitmask;
          SET(nbitmask,x,0);
          SET(nbitmask,(x+1),0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]);
        }

        continue;
      Label1:;
        // x 0
        // 0 x
        int color;
        if( !( ( GET(bitmask,x) && ( GET(bitmask,(x+1)) == 0 ) ) || ( GET(bitmask,(x+1)) && ( GET(bitmask,x) == 0 ) ) ) ) goto Label2;
        color = GET(bitmask,x) | GET(bitmask,(x+1));
        if( STAR ) {
          // 0 0
          if( ((color==1)?2:3) == field[y][x] ) {
            nbitmask = bitmask;
            SET(nbitmask,x,0);
            SET(nbitmask,(x+1),0);
            if( x == w-1 ) nbitmask = FIX(nbitmask);
            update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
          }
        } else {
          // x 0
          if( y+1 < h && field[y+1][x] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,color);
            SET(nbitmask,(x+1),0);
            if( x == w-1 ) nbitmask = FIX(nbitmask);


            update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
          }
          
          // 0 x
          if( x+1 < w && field[y][x+1] != 1 ) {
            nbitmask = bitmask;
            SET(nbitmask,x,0);
            SET(nbitmask,(x+1),color);

            if( x == w-1 ) nbitmask = FIX(nbitmask);
            update(dp[!phase][nbitmask],(dp[phase][bitmask]+1));
          }
        }
        continue;
      Label2:;
        // x x
        if( !( GET(bitmask,x) && GET(bitmask,(x+1)) ) ) goto Label3;
        if( GET(bitmask,x) != GET(bitmask,(x+1)) ) goto Label3;

        color = GET(bitmask,x);
        
        // 0 0
        if( !STAR ) {
          nbitmask = bitmask;
          SET(nbitmask,x,0);
          SET(nbitmask,(x+1),0);
          if( x == w-1 ) nbitmask = FIX(nbitmask);
          update(dp[!phase][nbitmask],dp[phase][bitmask]+1);
        }
      Label3:;

      }
      if( field[y][x] == 2 || field[y][x] == 3 ) initter = false;
      rep(i,_size) dp[phase][state[i]] = -1;
      if( encounter >= 4 && dp[!phase][0] != -1 ) {
        mini = min(mini,dp[!phase][0]);
      }
      phase = !phase;
    }
  }
  if( dp[phase][0] != -1 ) mini = min(mini,dp[phase][0]);
  if( mini != IINF ) printf("%d\n",mini-2);
  else puts("0");
}

int main(){
  while( scanf("%d %d",&h,&w), h|w ){
    rep(i,h) rep(j,w) scanf("%d",&field[i][j]);
    compute();
  }
  return 0;
}
```