题目描述

有只含数字1-9的字符串s。现在要求在字符中插入若干加号，使得字符串成为一个加法算式。（也可以一个都不加）要使得计算结果是m的倍数，最少需要添加多少加号？

如果所有插入加号的方案都无法得到m的倍数，输出−1

输入样例1

88239 8

输出样例1

1

输入样例2

153 5

输出样例2

-1

输入样例3

9999999999 99999

输出样例3

0

s不超过25

2<=m<=1e9