CF2020A Find Minimum Operations

You are given two integers $ n $ and $ k $ . In one operation, you can subtract any power of $ k $ from $ n $ . Formally, in one operation, you can replace $ n $ by $ (n-k^x) $ for any non-negative integer $ x $ . Find the minimum number of operations required to make $ n $ equal to $ 0 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The only line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 10^9 $ ).

For each test case, output the minimum number of operations on a new line.

In the first test case, $ n = 5 $ and $ k = 2 $ . We can perform the following sequence of operations: 1. Subtract $ 2^0 = 1 $ from $ 5 $ . The current value of $ n $ becomes $ 5 - 1 = 4 $ . 2. Subtract $ 2^2 = 4 $ from $ 4 $ . The current value of $ n $ becomes $ 4 - 4 = 0 $ . It can be shown that there is no way to make $ n $ equal to $ 0 $ in less than $ 2 $ operations. Thus, $ 2 $ is the answer. In the second test case, $ n = 3 $ and $ k = 5 $ . We can perform the following sequence of operations: 1. Subtract $ 5^0 = 1 $ from $ 3 $ . The current value of $ n $ becomes $ 3 - 1 = 2 $ . 2. Subtract $ 5^0 = 1 $ from $ 2 $ . The current value of $ n $ becomes $ 2 - 1 = 1 $ . 3. Subtract $ 5^0 = 1 $ from $ 1 $ . The current value of $ n $ becomes $ 1 - 1 = 0 $ . It can be shown that there is no way to make $ n $ equal to $ 0 $ in less than $ 3 $ operations. Thus, $ 3 $ is the answer.