In ancient times, Romans constructed numerous water ways to supply water to cities and industrial sites. These water ways were amongst the greatest engineering feats of the ancient world.

These water ways contributed to social infrastructures which improved people's quality of life. On the other hand, problems related to the water control and the water facilities are still interesting as a lot of games of water ways construction have been developed.

Your task is to write a program which reads a map and computes the minimum possible cost of constructing water ways from sources to all the cities.



<image>



As shown in Figure 1, the map is represented by H × W grid cells, where each cell represents source, city, flatland, or obstacle.

You can construct only one water way from a source, but there are no limitations on the length of that water way and it can provide water to any number of cities located on its path. You can not construct water ways on the obstacles.

Your objective is to bring water to all the city and minimize the number of cells which represent water ways. In the Figure 1, water ways are constructed in 14 cells which is the minimum cost.

The water ways must satisfy the following conditions:

* a water way cell is adjacent to at most 2 water way cells in four cardinal points.
* a source cell is adjacent to at most 1 water way cell in four cardinal points.
* there is no path from a source to other sources through water ways.

Constraints

* Judge data contains at most 60 data sets.
* 3 ≤ H, W ≤ 10
* 1 ≤ the number of sources, the number of cities ≤ 8
* The map is surrounded by obstacles.
* Sources are not adjacent each other(on the left, right, top and bottom)
* There is a solution.

Input

The input consists of multiple datasets. Each dataset consists of:


H W
H × W characters


The integers H and W are the numbers of rows and columns of the map. H × W characters denote the cells which contain:

* 'P': source
* '*': city
* '.': flatland
* '#': obstacle



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

Output

For each dataset, print the minimum cost to construct the water ways.

Examples

Input

3 8
########
#P....*#
########
10 10
##########
#P.......#
#..#*....#
#..#*.#.*#
#.....#*.#
#*.......#
#..##....#
#...#.P..#
#P......P#
##########
0 0


Output

5
14


Input

3 8

P....*#

10 10

P.......#
..#*....#
..#*.#.*#
.....#*.#
*.......#
..##....#
...#.P..#
P......P#

0 0


Output

5
14
#include <bits/stdc++.h>
using namespace std;
struct Point {
  int x, y;
};
const int IINF = INT_MAX;
const char PATH = '$';
int h, w, s_size, c_size, bitIndex[12][12];
char c[12][12];
Point source[12], city[12], path[12];
int limit, next_limit;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int mini;
int bc[1 << 9];
int mani[12];
int initial_heuristic() {
  int sum = 0;
  for (int i = 0; i < c_size; i++) {
    mani[i] = IINF;
    for (int j = 0; j < s_size; j++)
      mani[i] = min(
          mani[i], abs(city[i].x - source[j].x) + abs(city[i].y - source[j].y));
    for (int j = 0; j < c_size; j++)
      if (j != i)
        mani[i] = min(mani[i],
                      abs(city[i].x - city[j].x) + abs(city[i].y - city[j].y));
    sum += mani[i];
  }
  return sum;
}
int get_heuristic(int sp, int bitmask) {
  int sum = 0;
  for (int i = 0; i < c_size; i++)
    if (!((bitmask >> i) & 1)) {
      mani[i] = min(mani[i],
                    abs(path[sp].x - city[i].x) + abs(path[sp].y - city[i].y));
      sum += mani[i];
    }
  return sum;
}
bool head[12][12];
bool opt[12][12];
int blocks;
void print_field() {
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cout << c[i][j];
    }
    puts("");
  }
}
void dfs(int sp, int bitmask, int prev, int step) {
  if (step + (c_size - bc[bitmask]) >= mini) return;
  if (sp >= s_size) return;
  if (bitmask == ((1 << c_size) - 1)) {
    mini = step;
    return;
  }
  int res = rand() % 100;
  if (res == 1 || res == 4 || res == 71 || res == 22 || res == 0) return;
  for (int dir = 0; dir < 4; dir++) {
    if (prev != -1 && (prev + 2) % 4 == dir) continue;
    int nx = path[sp].x + dx[dir], ny = path[sp].y + dy[dir];
    if (c[ny][nx] == 'P' || c[ny][nx] == '#' || c[ny][nx] == PATH) continue;
    bool success = true;
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
      int nx2 = nx + dx[i], ny2 = ny + dy[i];
      if (c[ny2][nx2] == PATH || c[ny2][nx2] == 'P') ++cnt;
    }
    if (cnt != 1) success = false;
    if (!success) continue;
    Point pp = path[sp];
    char pc = c[ny][nx];
    int nbitmask = bitmask;
    bool fin = false;
    if (c[ny][nx] == '*') nbitmask |= (1 << bitIndex[ny][nx]), fin = true;
    path[sp] = (Point){nx, ny};
    c[ny][nx] = PATH;
    swap(head[path[sp].y][path[sp].x], head[ny][nx]);
    dfs(sp, nbitmask, dir, step + 1);
    swap(head[path[sp].y][path[sp].x], head[ny][nx]);
    path[sp] = pp;
    c[ny][nx] = pc;
    if (fin) return;
  }
  dfs(sp + 1, bitmask, -1, step);
}
int compute() {
  mini = h * w - s_size - blocks;
  dfs(0, 0, -1, 0);
  return mini;
}
int main() {
  srand((unsigned int)time(NULL));
  for (int i = 0; i < (1 << 9); i++) bc[i] = __builtin_popcount(i);
  while (scanf(" %d %d", &h, &w), h | w) {
    s_size = c_size = 0;
    blocks = 0;
    for (int i = 0; i < h; i++)
      for (int j = 0; j < w; j++) {
        head[i][j] = false;
        scanf(" %c", &c[i][j]);
        if (c[i][j] == 'P') {
          source[s_size] = path[s_size] = (Point){j, i};
          s_size++;
          head[i][j] = true;
        }
        if (c[i][j] == '*') {
          city[c_size] = (Point){j, i};
          bitIndex[i][j] = c_size++;
        }
        if (c[i][j] == '#') ++blocks;
      }
    printf("%d\n", compute());
  }
  return 0;
}
