Given two integers N and M  you have to find out an integer which is a power of M and is nearest to N.
Note: If there are multiple answers possible to, print the greatest number possible.
 
Example 1:
Input:
N = 6, M = 3
Output:
9
Explanation:
Both 3 (3^{1}) and 9 (3^{2}) are equally
near to 6. But 9 is greater,
so the Output is 9.
Example 2:
Input:
N = 3, M = 2
Output:
4
Explanation:
Both 2 (2^{1}) and 4 (2^{2}) are equally
near to 3. But 4 is greater,
so the Output is 4.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function nearestPower() which takes 2 Integers N and M as input and returns the answer.
 
Expected Time Complexity: O(max(log(N),log(M)))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N,M <= 10^{9}

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(max(log(N),log(M)))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def nearestPower(self, N , M):

        # code here

Solutions:
from math import log

class Solution:

	def nearestPower(self, n, m):
		if n == m:
			return 1
		thres = log(n) // log(m)
		res1 = abs(n - m ** thres)
		res2 = abs(n - m ** (thres + 1))
		if res1 == res2:
			return int(m ** (thres + 1))
		elif res1 > res2:
			return int(m ** (thres + 1))
		else:
			return int(m ** thres)


class Solution:

	def nearestPower(self, N, M):
		result = M
		while result < N:
			result *= M
		diff1 = abs(N - result)
		prev = result // M
		diff2 = abs(N - prev)
		if diff2 <= diff1:
			result = prev
		return result


import math

class Solution:

	def nearestPower(self, N, M):
		if M == 1 or M > N:
			return 1
		a = int(math.log(N) // math.log(M))
		if N - M ** a < M ** (a + 1) - N:
			return M ** a
		return M ** (a + 1)


import math

class Solution:

	def nearestPower(self, N, K):
		if N == 1 and K == 1:
			return 1
		else:
			lg = math.log(N) // math.log(K)
			a = int(pow(K, lg))
			b = int(pow(K, lg + 1))
			if N - a < b - N:
				return a
			return b


class Solution:

	def nearestPower(self, N, M):
		i = 0
		curr = M
		while curr ** i < N:
			i += 1
		i -= 1
		if N - curr ** i < curr ** (i + 1) - N:
			return curr ** i
		return curr ** (i + 1)


from math import log

class Solution:

	def nearestPower(self, N, M):
		if N == M:
			return 1
		thres = log(N) // log(M)
		res1 = abs(N - M ** thres)
		res2 = abs(N - M ** (thres + 1))
		if res1 == res2:
			return int(M ** (thres + 1))
		elif res1 > res2:
			return int(M ** (thres + 1))
		else:
			return int(M ** thres)


class Solution:

	def nearestPower(self, N, M):
		i = 0
		while True:
			x = M ** i
			if x >= N:
				break
			i += 1
		if x == N:
			return x
		elif abs(x - N) <= abs(x // M - N):
			return x
		else:
			return x // M


class Solution:

	def nearestPower(self, N, M):
		m = M
		ans = 1
		while M < N:
			ans = M
			M = M * m
		if abs(N - ans) >= abs(M - N):
			return M
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		ob = Solution()
		print(ob.nearestPower(N, M))


from math import log

class Solution:

	def nearestPower(self, N, M):
		if N == M:
			return 1
		powValue = log(N) // log(M)
		res1 = abs(N - M ** powValue)
		res2 = abs(N - M ** (powValue + 1))
		if res1 >= res2:
			return int(M ** (powValue + 1))
		else:
			return int(M ** powValue)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		ob = Solution()
		print(ob.nearestPower(N, M))


import math

class Solution:

	def nearestPower(self, N, M):
		if M == 1:
			return 1
		x = int(math.log(N, M))
		y = pow(M, x)
		z = pow(M, x + 1)
		if N - y < z - N:
			return y
		else:
			return z


import math

class Solution:

	def nearestPower(self, N, M):
		if M == 1 or N < M:
			return 1
		ans = math.log(N, M)
		t1 = int(M ** int(ans))
		t2 = int(M ** (int(ans) + 1))
		if t2 - N < N - t1:
			return t2
		elif t2 - N > N - t1:
			return t1
		else:
			return N


class Solution:

	def nearestPower(self, n, m):
		val = m
		maxi = n - 1
		if m == 1:
			return 1
		if n == m:
			return n
		if n < m:
			if abs(n - m) > n - 1:
				return 1
			return m
		while abs(n - m) > abs(n - m * val):
			m = m * val
		return m


class Solution:

	def nearestPower(self, N, M):
		f = 1
		x = M
		while M < N:
			f = M
			M = M * x
		if N - f < M - N:
			return f
		else:
			return M


class Solution:

	def nearestPower(self, N, M):
		import math
		if M == 1:
			return 1
		a = math.log(N) // math.log(M)
		b = int(math.pow(M, a))
		c = int(math.pow(M, a + 1))
		if N - b < c - N:
			return b
		return c


class Solution:

	def nearestPower(self, N, M):
		ans = 1
		x = M
		while M < N:
			ans = M
			M = M * x
		if abs(N - ans) >= abs(M - N):
			return M
		return ans


class Solution:

	def nearestPower(self, N, M):
		if M == N:
			return M
		i = 0
		ans = 0
		ans1 = 0
		while True:
			if M ** i <= N:
				ans = M ** i
			else:
				ans1 = M ** i
				break
			i = i + 1
		if N - ans < ans1 - N:
			return ans
		else:
			return ans1


import math

class Solution:

	def nearestPower(self, N, M):
		if M > 1:
			temp = math.floor(math.log(N) // math.log(M))
			low = M ** temp
			high = low * M
			if N - low < high - N:
				return low
			else:
				return high
		else:
			return 1


class Solution:

	def nearestPower(self, N, M):
		X = M
		while X < N:
			X *= M
		if N - X / M < X - N:
			X /= M
		if N > M:
			return int(X)
		else:
			return 1


class Solution:

	def nearestPower(self, B, A):
		if A == B:
			return A
		if B < A:
			if A - B < B - 1:
				return A
			else:
				return 1
		c = 1
		b = B
		while b // A != 0:
			b //= A
			c += 1
		if A ** c - B > B - A ** (c - 1):
			return A ** (c - 1)
		else:
			return A ** c


class Solution:

	def nearestPower(self, N, M):
		n = 1
		u = 1
		for i in range(1, N):
			if pow(M, i) <= N:
				n = pow(M, i)
			else:
				break
		u = n * M
		if u - N <= N - n:
			return u
		else:
			return n


class Solution:

	def nearestPower(self, N, M):
		i = 0
		min = 0
		max = 0
		while 1:
			if M ** i == N:
				return M ** i
				break
			elif M ** i > N:
				min = M ** i - N
				break
			else:
				max = N - M ** i
			i = i + 1
		if min > max:
			return abs(max - N)
		elif max > min:
			return min + N
		else:
			return min + N


import math

class Solution:

	def nearestPower(self, a, b):
		if math.log(b) == 0:
			return a
		lowestpower = math.log(a) / math.log(b)
		A = pow(b, math.floor(lowestpower))
		B = A * b
		if abs(A - a) < abs(B - a):
			return A
		else:
			return B