A small vineyard ages its wine in oak casks numbered with consecutive positive integers as they enter the cellar. Before a tasting rotation, the cellar master picks one cask whose number is at least a given starting id, and whose decimal digits multiply together to a total that divides evenly by the number of tasting stations set up that day (so the cask's contents can later be portioned into equal shares with nothing left over). Given the starting cask id n and the station count t, find the smallest valid cask number.
The digit product of a single-digit number is the digit itself. If any digit of a candidate number is 0, its digit product is 0, and 0 is considered divisible by every t.
A single line containing two integers n and t, separated by a space.
Print a single integer: the smallest integer m with m >= n such that the product of the decimal digits of m is divisible by t. Such an m always exists within a bounded distance of n.
Example 1
Input
5 7
Expected
7
Explanation
Starting at 5: digit product of 5 is 5 (5 % 7 != 0); of 6 is 6 (6 % 7 != 0); of 7 is 7, and 7 % 7 == 0, so 7 is the first valid cask number.
Example 2
Input
15 3
Expected
16
Explanation
15 has digit product 1*5=5 (5 % 3 != 0). 16 has digit product 1*6=6, and 6 % 3 == 0, so the answer is 16.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →