CONTINUOUS NIVEN NUMBERS | Code vita 2017

Problem Description:

In recreational mathematics, a Niven number in a given number base, is an integer that is divisible by the sum of its digits when written in that base. For example, in base 10, 18 is a Niven number since 18 is divisible by 1+8 = 9. Also, 12001 in base 3 is also a Niven number since the sum of the digits is 4 (which is 11 in base 3) divides 12001 (12001 = 1021 x 11).

Given a base b, any number n < b is trivially a Niven number. We will ignore this case.

Given a base b, and a positive integer T, find the lowest number L such that L, L+1, ..., L+T-1 are all Niven numbers but neither L-1 nor L+T are Niven numbers.

Input Format:         

First line contains two integers, b and T

Output Format:

A single integer L such that L, L+1, ..., L+T-1 are all Niven numbers but neither L-1 nor L+T are Niven numbers.

Constraints:

2 ≤ b ≤ 10

1 < T < 7

Example 1

Input

10 4

Output

510

Explanation

510, 511, 512 and 513 are Niven numbers and 514 is not a Niven number. Also 509 is not a Niven number. It can be seen that for N < 510, no four consecutive numbers are Niven numbers.

Example 2

Input

5 5

Output

44

Explanation

44 in base 5 is equivalent to 24 in base 10. Clearly, sum of the digits is 8 = 13 in base 5 and 13 x 3 = 44 in base 5 and hence 44 is a Niven number. Similarly we can see 44+1 = 100, 101, 102 and 103 in base 5 are also Niven numbers. 104 is not a Niven number.