Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS10ADIV - Another Divisibility Problem

You are given a positive base-2 integer of at most 100 digits and a base-10 integer in the range [1, 10^6]. You are to find the minimum number of bit switch operations to perform in the first number in order to make it divisible by the second. Available operations are:

  • Make a '0' turn to '1'.
  • Make a '1' turn to '0'.

 

Input

Input consists of exactly two lines. The first one contains a binary number and the second contains a decimal number as described above.

Output

Print the minimum number of operations required on a single line.

Example

Input:
111000111
9

Output:
2

Turning the leftmost and the rightmost digit (both 1) into 0 is one of the possible solutions for the example.

111000111 -> 011000110
0110001102 mod 910 = 0

Scoring

Solving this problem you score 10 points.


Added by:Yandry Perez
Date:2010-05-17
Time limit:0.200s-2.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC GAWK MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.