Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

This round has an unusual addition to the rules. For each problem you must use distinct language. Thus, if you have a submission that has passed at least one test or is being tested at the moment, then for this task you can use only this language and can not use it for other tasks. More details can be read by the link. Different implementations of the same language are considered to be the same language (for example, in C++ you can only solve one problem, regardless of the exact chosen compiler).

No tag edit access

E. Big Number and Remainder

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputStepan has a very big positive integer.

Let's consider all cyclic shifts of Stepan's integer (if we look at his integer like at a string) which are also integers (i.e. they do not have leading zeros). Let's call such shifts as good shifts. For example, for the integer 10203 the good shifts are the integer itself 10203 and integers 20310 and 31020.

Stepan wants to know the minimum remainder of the division by the given number *m* among all good shifts. Your task is to determine the minimum remainder of the division by *m*.

Input

The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.

The second line contains the integer *m* (2 ≤ *m* ≤ 10^{8}) — the number by which Stepan divides good shifts of his integer.

Output

Print the minimum remainder which Stepan can get if he divides all good shifts of his integer by the given number *m*.

Examples

Input

521

3

Output

2

Input

1001

5

Output

0

Input

5678901234567890123456789

10000

Output

123

Note

In the first example all good shifts of the integer 521 (good shifts are equal to 521, 215 and 152) has same remainder 2 when dividing by 3.

In the second example there are only two good shifts: the Stepan's integer itself and the shift by one position to the right. The integer itself is 1001 and the remainder after dividing it by 5 equals 1. The shift by one position to the right equals to 1100 and the remainder after dividing it by 5 equals 0, which is the minimum possible remainder.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 19:54:49 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|