Ishaan wants to intern at GeeksForGeeks but for that he has to go through a test. There are n candidates applying for the internship including Ishaan and only one is to be selected.
Since he wants to qualify he asks you to help him. The test is as follows.
The candidates are asked to stand in a line at positions 1 to n and given a number k. Now, every kth candidate remains and the rest are eliminated. This is repeated until the number of candidates are less than k.
Out of the remaining candidates, the one standing at smallest position is selected. You need to tell Ishaan at position he must stand to get selected.
Example 1:
Input 
n = 30
k = 3
Output 
27
Explaination 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
3 6 9 12 15 18 21 24 27 30
9 18 27
27
Example 2:
Input 
n = 18
k = 3
Output  
9
Explaination 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
3 6 9 12 15 18
9 18 (less than k)
9
Your Task :
You don't need to read input or print anything. Your task is to Complete the function getCandidate() which takes two integer n and k as input parameters, and returns the answer.
Expected Time Complexity: O(log_{k}n)
Expected Auxiliary Space: O(1)
Constraints 
1 <= n <= 10^{5}
2 <= k <= 10

Difficulty: EASY
Tags: Mathematics

Complete search
Skill types: Complete search
Expected Time Complexity: O(log_{k}n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



def getCandidate(n, k):

    #complete the function here

Solutions:
def getCandidate(n, k):
	cnt = 0
	while n >= k:
		n = n // k
		cnt += 1
	return k ** cnt


def getCandidate(n, k):
	i = 0
	while True:
		i = i + 1
		b = k ** i
		if b > n:
			break
	return k ** (i - 1)


def getCandidate(n, k):
	c = 0
	temp = n
	while temp >= k:
		temp = temp // k
		c = c + 1
	return k ** c


def getCandidate(n, k):
	count = 0
	while n >= k:
		n = n / k
		count += 1
	return k ** count


def getCandidate(n, k):
	j = k
	while j <= n:
		j *= k
	return j // k


import math

def getCandidate(n, k):
	temp = n
	count = 0
	while temp >= k:
		temp = temp // k
		count += 1
	ans = int(math.pow(k, count))
	return ans


import math

def getCandidate(n, k):
	cnt = 0
	while n >= k:
		n = n // k
		cnt += 1
	return k ** cnt


def getCandidate(n, k):
	i = 0
	while n >= k:
		n = n // k
		i = i + 1
	ans = int(k ** i)
	return ans


def getCandidate(n, k):
	jump = 0
	while n >= k:
		n = n // k
		jump += 1
	return k ** jump


def getCandidate(n, k):
	count = 0
	temp = n
	while temp >= k:
		temp = temp // k
		count += 1
	return pow(k, count)


def getCandidate(l, k):
	count = 0
	while l >= k:
		l //= k
		count += 1
	return k ** count


def getCandidate(n, k):
	m = k
	while True:
		if m > n:
			return m // k
		m *= k


def getCandidate(n, k):
	pre = 0
	v = k
	while k <= n:
		pre = k
		k *= v
	return pre


def getCandidate(n, k):
	i = k
	while i * k <= n:
		i *= k
	return i


def getCandidate(n, k):
	b = 0
	i = 1
	m = 0
	if n > k:
		while m <= n:
			m = k ** i
			b = m
			i += 1
	else:
		return k
	return b // k


def getCandidate(n, k):
	no = k
	c = n // k
	while c >= k:
		c = c // k
		no *= k
	return no


def getCandidate(n, k):
	num = k
	while num <= n:
		num = num * k
	return int(num / k)


def getCandidate(n, k):
	num = 0
	while n >= k:
		n = n // k
		num += 1
	return k ** num
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		print(getCandidate(n, k))


def getCandidate(n, k):
	c = k
	while c <= n:
		d = c
		c = c * k
	return d
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		print(getCandidate(n, k))


def getCandidate(n, k):
	i = 1
	x = 1
	while n >= x:
		ans = x
		x = k ** i
		i += 1
	return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		print(getCandidate(n, k))


def getCandidate(n, k):
	ans = 1
	while n >= k:
		ans = ans * k
		n = int(n / k)
	return ans


from math import log, floor

def getCandidate(n, k):
	return k ** floor(log(n, k))


def getCandidate(n, k):
	i = 0
	while n >= k:
		n = n // k
		i = i + 1
	return k ** i


def getCandidate(n, k):
	a = 0
	b = 0
	while k ** a <= n:
		b = k ** a
		a += 1
	return b


def getCandidate(n, k):
	count = 0
	a = pow(k, count)
	while a <= n:
		count += 1
		a = pow(k, count)
	return pow(k, count - 1)


def getCandidate(n, k):
	c = 0
	while n >= k:
		n = n // k
		c = c + 1
	return int(pow(k, c))


def getCandidate(n, k):
	value = k
	while value <= n:
		value = value * k
		v = int(value / k)
	return v


def getCandidate(n, k):
	val = k
	while val <= n:
		val *= k
	return int(val / k)


import math

def getCandidate(n, k):
	a = int(math.log(n, k))
	output = k ** a
	return output


def getCandidate(n, k):
	i = 1
	while pow(k, i) < n:
		i += 1
	if pow(k, i) == n:
		return pow(k, i)
	else:
		return pow(k, i - 1)


def getCandidate(n, k):
	count = 0
	while n >= 1:
		n = n // k
		count += 1
		if n < k:
			break
	return k ** count


def getCandidate(n, k):
	fnal = 1
	li = 1
	while n >= k:
		n = n // k
		li = li * k
	return li


def getCandidate(n, k):
	c = 0
	p = k ** c
	while p <= n:
		c += 1
		p = k ** c
	return k ** (c - 1)


def getCandidate(n, k):
	c = []
	i = 0
	while k ** i < n or k ** i == n:
		f = k ** i
		i = i + 1
		c.append(f)
	return c[-1]


def getCandidate(n, k):
	count = 0
	p = pow(k, count)
	while p <= n:
		count += 1
		p = pow(k, count)
	return pow(k, count - 1)