Minimum Weights for Balance Scale

In this problem, you are given two positive integers n and m. We have an infinite set of weights with masses n¹, n², n³, …. Using these weights, you need to determine the minimum number of weights required to measure an object of weight m on a two‐pan balance scale. The weights can be placed on either pan. That is, if you put a weight on the same pan as the object it effectively subtracts from the object’s weight, otherwise it adds to the counterbalance. Formally, if you select a set of weights (each weight can be used at most once) corresponding to exponents k₁, k₂, …, k_r with coefficients d_i ∈ { -1, 0, 1 } then the balancing condition is:

\( m = \sum_{i=1}^{r} d_i \cdot n^{k_i} \)

Since the available weights start from n¹ (i.e. the weight 1 is not available), a necessary condition for m to be measurable is that m is divisible by n. You are guaranteed that the input satisfies this condition so that a solution exists.

A standard approach is to first divide m by n and then represent the resulting number in a balanced numeral system with base n using only the digits -1, 0 and 1. The answer is the number of nonzero digits in this representation, which corresponds to the minimum number of weights used.

Note: You can assume that the input is such that the required representation exists, and you only need to output the minimal number of weights.

inputFormat

The input consists of one line with two space-separated positive integers n and m. It is guaranteed that m is divisible by n.

outputFormat

Output a single integer – the minimum number of weights needed to measure the object.

sample

3 12

2