For a positive, non-zero integer N, find the minimum count of numbers of the form X^{(i-1)}, where X is a given non-zero, non-negative integer raised to the power i-1 where (1 ≤ i ≤ 12), so that they sum up to form the number N exactly.
Example 1:
Input: N = 10, X = 2
Output: 2
Explaination: The minimal summing is 8 + 2. 
Here both 8 and 2 are obtained from 2 raising 
it to the power 3 and 1 respectively.
Example 2:
Input: N = 38, X = 3
Output: 4
Explaination: The minimal summing is 
27 + 9 + 1 + 1. Where all the numbers are 
powers of 3.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minimalSum() which takes N and X as input parameters and returns the minimum number of values of some exponent of X required to make the number N.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{8}
2 ≤ X ≤ 5

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3

class Solution:
    def minimalSum(self, N, X):
        # code here

Solutions:
class Solution:

	def minimalSum(self, N, X):
		count = 0
		i = 11
		while N > 0:
			if N >= X ** i:
				N = N - X ** i
				count += 1
			else:
				i -= 1
		return count


class Solution:

	def minimalSum(self, n, x):
		l = []
		s = 0
		j = 0
		d = n
		count = 1
		for i in range(11, 0, -1):
			l.append(x ** i)
		while j < len(l):
			while l[j] <= n:
				n = n - l[j]
				count += 1
				s = s + l[j]
			j = j + 1
		if d == s:
			return count - 1
		else:
			return count + (d - s) - 1


class Solution:

	def minimalSum(self, N, X):
		ans = 0
		while N > X ** 11:
			ans += 1
			N -= X ** 11
		while N > 0:
			if N % X != 0:
				ans += N % X
			N = N // X
		return ans


class Solution:

	def minimalSum(self, N, X):
		digs = 0
		maxSummand = X ** 11
		while N >= X ** 11:
			digs += 1
			N -= maxSummand
		while N:
			if N % X:
				digs += N % X
			N //= X
		return digs


class Solution:

	def minimalSum(self, N, X):
		exp = 11
		coefficients = []
		valid = 0
		while exp >= 0:
			quot = N // X ** exp
			coefficients.append(0)
			if quot != 0:
				N = N - quot * X ** exp
				coefficients[11 - exp] = quot
			exp = exp - 1
			valid = valid + quot
		return valid


class Solution:

	def minimalSum(self, N, X):
		counter = 0
		p = 11
		while N >= 1:
			while X ** p > N:
				p -= 1
			counter += 1
			N -= X ** p
		return counter


from math import log, floor

class Solution:

	def minimalSum(self, N, X):
		count = 0
		while N != 0:
			power = floor(log(N, X))
			if power > 11:
				power = 11
			N = N - X ** power
			count += 1
		return count


class Solution:

	def minimalSum(self, N, X):
		c = 0
		while N != 0:
			p = 1
			d = 0
			while p * X <= N and d < 11:
				d += 1
				p = p * X
			N = N - p
			c += 1
		return c


class Solution:

	def minimalSum(self, N, X):
		powers = [X ** (i - 1) for i in range(12, 0, -1)]
		i = 0
		d = N
		sums = []
		while d > 0:
			while powers[i] > d:
				i += 1
			sums.append(i)
			d -= powers[i]
		return len(sums)


class Solution:

	def minimalSum(self, N, X):
		count = 0
		for x in range(11, -1, -1):
			count += int(N / X ** x)
			N = int(N % X ** x)
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		X = int(input())
		ob = Solution()
		print(ob.minimalSum(N, X))