#include <cstdio>
#include <cstring>
#include <algorithm>

#define KONJ 42 - 42
#define INF 105

using namespace std;

int N, len;
char s[150];
int niz[150];
short memo[110][1000010];

int solve( int curr, int val ){

    int ret = 0;
    if ( curr == len ){ return INF; }
    if ( val == 0 ){ return memo[curr][val] = 0; }
    if ( memo[curr][val] > 0 ){ return memo[curr][val]; }

    ret = min( solve( curr + 1, val ), 1 + solve( curr + 1, ( val + niz[ curr + 1 ] ) % N ) );
    return memo[curr][val] = ret;

}

int main( void ){

    scanf( "%s", s ); len = strlen( s );
    scanf( "%d", &N );

    int ostatak = 0;
    for ( int i = len - 1; i >= 0; --i ){
        if ( i == len - 1 ){ niz[i] = 1 % N; } else { niz[i] = niz[i + 1] * 2; niz[i] %= N; }
        if ( s[i] == '1' ){ ostatak += niz[i]; ostatak %= N; }
        // printf( "%d %c %d %d\n", ostatak, s[i], niz[i], i );
    }

    for ( int i = 0; i < len - 1; ++i ){
        if ( s[i] == '1' ){ niz[i] = N - niz[i]; }
    }

    //printf( "%d\n", ostatak );
    printf( "%d\n", solve( 0, ostatak ) );

    return KONJ;

}