#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int mxn = 1e3+10;
const int mod = 998244353;
int pa[2*mxn], sz[2*mxn], h ,w;
string mt[mxn];

int find(int v) {
	if(v==pa[v]) return v;
	return pa[v] = find(pa[v]);
}

void unite(int a, int b) {
	a = find(a); b = find(b);
	if(a!=b) pa[b] = a, sz[a]+=sz[b];
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin>>h>>w;
	for(int i=0; i<h; i++) cin>>mt[i];

	for(int i=0; i<h+w; i++) pa[i] = i, sz[i] = 1;

	unite(0, 0+h); unite(0, w-1+h); unite(h-1, 0+h); unite(h-1, w-1+h); 

	for(int i=0; i<h; i++) for(int j=0;j<w; j++) if(mt[i][j]=='#') unite(i, j+h);

	set<pair<int, int> > s; for(int i=0;i<w+h; i++) s.insert(make_pair(find(i), sz[find(i)]));

	int row = 0, col = 0;
	for(auto x:s) {
		if(x.second>=2) row++, col++;
		else if(x.first<h) row++;
		else col++;
	}

	int ans = min(row, col)-1;
	cout << ans << '\n';

	return 0;
}
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = n - 1; i >= 0; --i)

template<typename T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } else return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } else return false; }

using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll inf = 1'000'000'000'000'000'001;

ll base_n(string x, ll n) {
    ll ret = 0;
    for (char c : x) {
        if (ret > inf / n) return -1;
        ret *= n;
        ret += (ll)c - '0';
    }
    return ret;
}

int main() {
    string x;
    ll m;
    cin >> x >> m;
    ll d = 0;
    for (char c : x) chmax(d, (ll)c - '0');
    if (x.size() == 1) {
        if (d <= m) cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    }
    ll ng = inf;
    ll ok = d;
    while (abs(ok - ng) > 1) {
        ll c = ok + (ng - ok) / 2;
        ll y = base_n(x, c);
        if (y < 0) {
            ng = c;
            continue;
        }
        if (y <= m) ok = c;
        else ng = c;
    }
    ll ans = ok - d;
    cout << ans << endl;
}