#include <bits/stdc++.h>

#define FOR(i,n)    for(lli i=0;i<(lli)(n);++i)
#define FORU(i,j,k) for(lli i=(j);i<=(lli)(k);++i)
#define FORD(i,j,k) for(lli i=(j);i>=(lli)(k);--i)

#define pb push_back
#define mt make_tuple

using namespace std;

using lli = long long int;
using pll = pair<lli, lli>;

using vi = vector<lli>;
using vvi = vector<vi>;
using pii = tuple<lli, lli>;
using vii = vector<pii>;
using vvii = vector<vii>;

#define X(a) get<0>(a)
#define Y(a) get<1>(a)
#define Z(a) get<2>(a)

string TYPE(const int*)          { return "%d";   }
string TYPE(const lli*)          { return "%lld"; }
string TYPE(const size_t*)       { return "%u";   }
string TYPE(const double*)       { return "%lf";  }
string TYPE(const char*)         { return "%c";   }
string TYPE(const char**)        { return "%s";   }
string TYPE(const unsigned int*) { return "%u";   }

const int MAX_BUF = 100*1000+42;
char buf[MAX_BUF];

void RD() {}
template<typename T, typename... Args> 
void RD(T* v, Args... args)
{
    scanf((" " + TYPE(v)).c_str(), v);
    RD(args...);
}
template<typename... Args> 
void RD(string* v, Args... args)
{
    scanf(" %s", buf);
    (*v) = buf;
    RD(args...);
}

template<class A, class B, typename... Args> 
void PR(bool nl, pair<A, B> p, Args... args);
void PR(bool nl = true)
{ if(nl) printf("\n"); }
template<typename T, typename... Args> 
void PR(bool nl, T v, Args... args)
{
    printf((TYPE(&v) + " ").c_str(), v);
    PR(nl, args...);
}
template<typename... Args> 
void PR(bool nl, string& v, Args... args)
{
    printf("%s", v.c_str());
    PR(nl, args...);
}
template<class A, class B, typename... Args> 
void PR(bool nl, pair<A, B> p, Args... args)
{
    PR(false, "{", p.first, ",", p.second, "}");
    PR(nl, args...);
}
template<typename... Args> 
void PR(Args... args)
{ PR(true, args...); }

const long long int oo = 1000*1000*1000;

struct Coord {
    int x, y;
    Coord(int x = 0, int y = 0) : x(x), y(y) {}
    Coord operator + (const Coord& droite) const
    { return Coord(x + droite.x, y + droite.y); }
};

struct AB {
    int k; vector<lli> arbre;
    AB(int _k = 20, lli def = 0) { k = _k;
        FOR(i, 1 << k)
            arbre.push_back(i < (1 << (k-1)) ? 0LL : def);
        FORD(i, ((1 << (k-1)) - 1), 1)
            arbre[i] = arbre[i << 1] + arbre[(i << 1) ^ 1];
    }
    void set(int i, lli x) { int feuille = i + (1 << (k-1));
        arbre[feuille] = x;
        iset(feuille >> 1);
    }
    void iset(int noeud) {
        if(noeud) {
            arbre[noeud] = arbre[noeud << 1] + arbre[(noeud << 1)  ^ 1];
            iset(noeud >> 1);
    }   }
    lli sum(int deb, int fin, int noeud = 1, int p = 0, int q = -1) {
        if(q < p) q = 1 << (k-1);
        if(deb <= p && q <= fin) return arbre[noeud];
        if(deb >= q || fin <= p) return 0LL;
        int mil = (p + q) / 2;
        return sum(deb, fin, noeud << 1, p, mil) + sum(deb, fin, (noeud << 1) ^ 1, mil, q);
    }
};

const int MAX_M = 10'000+42;

int dv[MAX_M][MAX_M];

int main()
{
    lli m, n; RD(&n, &m);
    if(m == 1 || m == 3) {
        PR(0);
        return 0;
    }
    lli k = 0, r = 1;
    int cnt = 0;
    lli period = 0, offset = 0;
    if(m == 9) {
        period = 9;
    } else {
        while(dv[k][r] == 0) {
            ++cnt;
            dv[k][r] = cnt;
            r = 10*r;
            k = (10*k + r/m) % m;
            r = r % m;
            //PR(cnt, k, r);
        }
        period = cnt - dv[k][r]+1;
        offset = dv[k][r]-1;
        //PR(k, r);
    }
    //PR(period, offset);
    if(n <= offset) {
        k = 0, r = 1;
        FOR(i, n) {
            r = 10*r;
            k = (10*k + r/m) % m;
            r = r % m;
        }
        PR(k);
        return 0;
    }
    //PR(cnt);
    n = ((n-offset) % period) + offset;
    k = 0, r = 1;
    FOR(i, n) {
        r = 10*r;
        k = (10*k + r/m) % m;
        r = r % m;
    }
    PR(k);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int64_t ans=0;
int sx,sy;
int H,W;
vector<vector<bool> > flag;
vector<vector<int> > vv;

void dfs(int x,int y,int num,int64_t count,char dir){
  if(num==0){
    if(sy==y-1){
      if(dir!='L'){
        count++;
      }
    }else if(sy==y+1){
      if(dir!='R'){
        count++;
      }
    }else if(sx==x-1){
      if(dir!='U'){
        count++;
      }
    }else if(sx==x+1){
      if(dir!='D'){
        count++;
      }
    }
    ans=max(ans,count);
    return;
  }
  for(auto &tmp:vv.at(x*W+y)){
    int nx=tmp/W;
    int ny=tmp%W;
    if(flag.at(nx).at(ny)){
      flag.at(nx).at(ny)=false;
      bool judge=true;
      char c=dir;
      if(ny==y-1){
        if(dir!='L'){
          judge=false;
          c='L';
        }
      }else if(ny==y+1){
        if(dir!='R'){
          judge=false;
          c='R';
        }
      }else if(nx==x-1){
        if(dir!='U'){
          judge=false;
          c='U';
        }
      }else if(nx==x+1){
        if(dir!='D'){
          judge=false;
          c='D';
        }
      }
      if(judge){
        dfs(nx,ny,num-1,count,c);
      }else{
        dfs(nx,ny,num-1,count+1,c);
      }
    }
  }
}

int main(){
  cin >> H >> W;
  vector<string> S(H);
  flag.resize(H+1,vector<bool>(W+1,false));
  vv.resize(H*W+W+1,vector<int>(H*W+W+1));
  for(int i=0;i<H;i++){
    cin >> S.at(i);
  }
  int num=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S.at(i).at(j)=='#'){
        if(S.at(i).at(j-1)=='.'){
          flag.at(i).at(j)=true;
          flag.at(i+1).at(j)=true;
          vv.at(i*W+j).emplace_back((i+1)*W+j);
          vv.at((i+1)*W+j).emplace_back(i*W+j);
        }
        if(S.at(i).at(j+1)=='.'){
          flag.at(i).at(j+1)=true;
          flag.at(i+1).at(j+1)=true;
          vv.at(i*W+j+1).emplace_back((i+1)*W+j+1);
          vv.at((i+1)*W+j+1).emplace_back(i*W+j+1);
        }
        if(S.at(i-1).at(j)=='.'){
          flag.at(i).at(j)=true;
          flag.at(i).at(j+1)=true;
          vv.at(i*W+j).emplace_back(i*W+j+1);
          vv.at(i*W+j+1).emplace_back(i*W+j);
        }
        if(S.at(i+1).at(j)=='.'){
          flag.at(i+1).at(j)=true;
          flag.at(i+1).at(j+1)=true;
          vv.at((i+1)*W+j).emplace_back((i+1)*W+j+1);
          vv.at((i+1)*W+j+1).emplace_back((i+1)*W+j);
        }
      }
    }
  }
  for(int i=0;i<H+1;i++){
    for(int j=0;j<W+1;j++){
      if(flag.at(i).at(j)){
        sx=i;
        sy=j;
        num++;
      }
    }
  }
  flag.at(sx).at(sy)=false;
  dfs(sx,sy,num-1,0,' ');
  cout << ans << endl;
  return 0;
}
