A disease is spreading through ChefLand!

The disease spreads as follows:
At the end of day 0, a single person is infected with the disease.
During the next 10 days, the number of infected people doubles each day, until the disease has spread to all people in ChefLand.
From day 11 onwards, the number of infected people triples each day, until the disease has spread to all people in ChefLand.

You are given the population of ChefLand N and a day D. How many people in ChefLand are infected at the end of day D?

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line containing two space-separated integers N and D — the population of ChefLand and the day for which you need to find the number of infected people, respectively.

------ Output Format ------ 

- For each test case, print one line containing a single integer — the number of infected people in ChefLand at the end of day D.

------ Constraints ------ 

$1 ≤ T ≤ 300$
$1 ≤ N ≤ 10^{8}$ 
$0 ≤ D ≤ 10^{8}$ 

------ subtasks ------ 

Subtask 1 (30 points): $D ≤ 20$

Subtask 2 (70 points): Original constraints

----- Sample Input 1 ------ 
4
100 3
2000 10
6000 11
10 11
----- Sample Output 1 ------ 
8
1024
3072
10
----- explanation 1 ------ 
Test Case 1: 
- At the end of day $1$, the number of infected people is $2 \times 1 = 2$.
- At the end of day $2$, the number of infected people is $2 \times 2 = 4$.
- At the end of day $3$, the number of infected people is $2 \times 4 = 8$.

Test Case 2: Following the rules in the statement, it can be seen that at the end of day $10$, the total number of infected people is $1024$.

Test Case 3: Note that starting at day $11$, the number of infected people triples each day, $3 \times 1024 = 3072$.

Test Case 4: At the end of day $3$, the number of infected people is $8$. Since there are only $10$ people in ChefLand (which is less than $2 \times 8 = 16$), at the end of day $4$ all people in ChefLand are infected and thus the number of infected people is $10$ for all days from day $4$ onwards, including day $11$.

Difficulty: EASY

Starter code:

Solutions:
t = int(input())
for ni in range(t):
	(n, d) = map(int, input().split())
	count = 1
	for nj in range(d):
		if count >= n:
			break
		elif nj < 10:
			count = count * 2
		else:
			count = count * 3
	print(min(n, count))


def power(a, b):
	ans = 1
	n = 1000000007
	while b > 0:
		if b & 1 != 0:
			ans = ans * (a % n) % n
		a = a % n * (a % n)
		b = b >> 1
	return ans
t = int(input())
for i in range(t):
	i = input().split()
	n = int(i[0])
	d = int(i[1])
	ip = 0
	if d <= 10:
		ip = power(2, d)
	if d > 10:
		ip = power(2, 10)
		ip = ip * power(3, d - 10)
	if ip <= n:
		print(ip)
	else:
		print(n)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	x = 1
	y = 1
	if n == 0:
		print(x)
	else:
		for i in range(d):
			if i < 10:
				x *= 2
			else:
				x *= 3
			if x > n:
				print(n)
				y = 0
				break
		if y == 1:
			print(x)


from math import log
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	if n <= 1024:
		print(min(2 ** min(d, 10), n))
	elif d <= 10:
		print(2 ** d)
	else:
		d -= 10
		left_time = min(log(n / 1024, 3), d)
		print(round(1024 * 3 ** left_time))


for _ in range(int(input())):
	(population, day) = map(int, input('').split())
	x = 1
	y = 1
	if day == 0:
		print(x)
	else:
		for i in range(day):
			if i < 10:
				x *= 2
			else:
				x *= 3
			if x > population:
				print(population)
				y = 0
				break
		if y == 1:
			print(x)


for j in range(int(input())):
	(m, d) = map(int, input().split())
	x = 1
	y = 1
	if d == 0:
		print(x)
	else:
		for j in range(d):
			if j < 10:
				x *= 2
			else:
				x *= 3
			if x > m:
				print(m)
				y = 0
				break
		if y == 1:
			print(x)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	x = 1
	flag = 0
	for j in range(1, d + 1):
		if j <= 10:
			x = x * 2
			if x >= n:
				print(n)
				flag = 1
				break
		else:
			x = x * 3
			if x >= n:
				print(n)
				flag = 1
				break
	if flag == 0:
		print(x)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	r = 1
	for i in range(d):
		if i <= 9:
			r = r * 2
		else:
			r = r * 3
		if r > n:
			break
	print(min(r, n))


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	c = 1
	for i in range(1, d + 1):
		if i <= 10:
			c *= 2
		else:
			c *= 3
		if c > n:
			break
	print(min(c, n))


T = int(input())
for _ in range(0, T):
	(n, d) = map(int, input().split())
	if d == 0:
		print(1)
	elif d <= 10:
		inf = 1
		while True:
			if inf >= n:
				break
			elif d == 0:
				break
			else:
				inf *= 2
				d -= 1
		print(min(inf, n))
	else:
		inf = 2 ** 10
		while True:
			if inf >= n:
				break
			elif d == 10:
				break
			else:
				inf *= 3
				d -= 1
		print(min(inf, n))


for i in range(int(input())):
	(n, d) = [int(x) for x in input().split()]
	res = 1
	for d in range(1, d + 1):
		if d <= 10:
			res *= 2
		elif d > 10:
			res *= 3
		if res > n:
			break
	print(min(res, n))


for i in range(int(input())):
	(n, d) = map(int, input().split())
	infected = 1
	for j in range(1, d + 1):
		if j <= 10:
			infected *= 2
		elif j >= 11:
			infected *= 3
		if infected > n:
			break
	print(min(infected, n))


for i in range(int(input())):
	(n, d) = map(int, input().split())
	infected = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 3072, 9216, 27648, 82944, 248832, 746496, 2239488, 6718464, 20155392, 60466176]
	if d <= 20:
		spreads = infected[d]
		if n <= spreads:
			print(n)
		else:
			print(spreads)
	else:
		print(n)


import sys
input = sys.stdin.readline
for i in range(int(input())):
	(hem, hen) = map(int, input().split())
	neh = 1
	for j in range(min(hen, 10)):
		neh *= 2
	for j in range(10, hen):
		neh *= 3
		if neh >= hem:
			break
	print(min(neh, hem))


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	if d == 0:
		print(1)
	else:
		(i, cnt) = (1, 1)
		while i <= d and cnt <= n:
			if i <= 10:
				if cnt * 2 > n:
					cnt = cnt + n - cnt
					break
				else:
					cnt = cnt * 2
			elif i > 10:
				if cnt * 3 > n:
					cnt = cnt + n - cnt
					break
				else:
					cnt = cnt * 3
			i = i + 1
		print(cnt)


import sys
input = sys.stdin.readline
for i in range(int(input())):
	(nju, dec) = map(int, input().split())
	cde = 1
	for j in range(min(dec, 10)):
		cde *= 2
	for j in range(10, dec):
		cde *= 3
		if cde >= nju:
			break
	print(min(cde, nju))


T = int(input())
for i in range(T):
	(N, D) = map(int, input().split())
	K = D - 10
	mult = 1
	for i in range(1, D + 1):
		if i <= 10:
			mult *= 2
		elif i >= 11:
			mult *= 3
		if mult > N:
			break
	print(min(mult, N))


t = input()
for c in range(0, int(t)):
	(n, d) = map(int, input().split())
	ans = 0
	if d <= 10:
		ans += 2 ** d
	else:
		ans += 1024
		d -= 10
		if d > 11:
			ans *= 3 ** 11
		else:
			ans *= 3 ** d
	if ans > n:
		print(n)
	else:
		print(ans)


import math
from sys import stdin, stdout
read = stdin.readline

def Covid(N, Days):
	spread = 0
	if Days <= 10:
		spread += 2 ** Days
	else:
		spread += 1024
		Days = Days - 10
		if Days > 11:
			spread = spread * 3 ** 11
		else:
			spread = spread * 3 ** Days
	if spread > N:
		print(N)
	else:
		print(spread)
numbertest = int(input())
for i in range(numbertest):
	(N, Days) = map(int, input().split())
	Covid(N, Days)


tests = int(input())
for i in range(tests):
	(n, d) = map(int, input().split())
	ans = 0
	if d <= 10:
		ans += 2 ** d
	else:
		ans += 1024
		d -= 10
		if d > 11:
			ans *= 3 ** 11
		else:
			ans *= 3 ** d
	if ans > n:
		print(n)
	else:
		print(ans)


for _ in range(int(input())):
	(n, d) = list(map(int, input().split(' ')))
	infected = 1
	if d <= 10:
		for i in range(1, d + 1):
			if infected < n:
				infected *= 2
			if infected >= n:
				infected = n
				break
	if d > 10:
		for i in range(1, 11):
			if infected < n:
				infected *= 2
			if infected >= n:
				infected = n
				break
		for i in range(11, d + 1):
			if infected < n:
				infected *= 3
			if infected >= n:
				infected = n
				break
	print(infected)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	z = 1
	for i in range(1, y + 1):
		if i <= 10:
			z = z * 2
		elif i >= 11:
			z = z * 3
		if z >= x:
			z = x
			break
	print(z)


T = int(input())
for i in range(T):
	(n, d) = map(int, input().split())
	i = 1
	for x in range(1, d + 1):
		if x >= 11:
			i *= 3
		elif x <= 10:
			i *= 2
		if i >= n:
			break
	print(min(n, i))


n = int(input())
while n > 0:
	p = 1
	(n1, d1) = map(int, input().split())
	for i in range(1, d1 + 1):
		if i <= 10:
			p *= 2
		else:
			p *= 3
		if p >= n1:
			break
	print(min(n1, p))
	n -= 1


noOfTestCases = int(input())
hashMap = {}
hitCounter = 0
daySpread = []
for iter in range(21):
	if iter + 1 <= 10:
		daySpread.append(2 ** (iter + 1))
	else:
		daySpread.append(1024 * 3 ** (iter + 1 - 10))
for _ in range(noOfTestCases):
	(P, D) = map(int, input().split())
	if D > 21:
		print(P)
	elif D == 0:
		print(1)
	else:
		print(daySpread[D - 1]) if daySpread[D - 1] < P else print(P)


test = int(input())
for i in range(test):
	lis = list(map(int, input().split()))
	N = lis[0]
	D = lis[1]
	sumval = 1
	for i in range(1, D + 1):
		if i <= 10:
			sumval *= 2
		if i > 10:
			sumval *= 3
		if sumval > N:
			print(N)
			break
	else:
		print(sumval)


for t in range(int(input())):
	(n, d) = map(int, input().split())
	i = 1
	c = 1
	while i <= d:
		if i < 11:
			c *= 2
		else:
			c *= 3
		if c >= n:
			c = n
			break
		i += 1
	print(c)


try:
	t = int(input())
	for i in range(t):
		(n, d) = map(int, input().split(' '))
		if d <= 10:
			ans = 2 ** d
			if ans <= n:
				print(ans)
			else:
				print(n)
		elif d > 10:
			ans = 1024
			if ans <= n:
				if d > 20:
					print(n)
				else:
					ans = ans * 3 ** (d - 10)
					if ans <= n:
						print(ans)
					else:
						print(n)
			else:
				print(n)
except:
	pass


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	ans = 1
	temp = 0
	if d > 10:
		temp = d - 10
		d -= temp
	if d > 0 and d <= 10:
		ans = 2 ** d
	if temp > 0:
		for i in range(temp):
			if ans > n:
				break
			ans = ans * 3
	if n < ans:
		print(n)
	else:
		print(ans)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	sum = 1
	for i in range(1, d + 1):
		if i >= 1 and i <= 10:
			sum = sum * 2
			if sum >= n:
				sum = n
				break
		elif i >= 11 and i <= n:
			sum = sum * 3
			if sum >= n:
				sum = n
				break
	print(sum)


import sys, math, string, random, array
count = 0
max = 0
min = 99

def solve():
	(n, d) = map(int, input().split())
	if d == 0:
		print('1')
	else:
		sum = 1
		count = 0
		for i in range(1, d + 1):
			if i > 10:
				sum *= 3
			else:
				sum *= 2
			if sum > n:
				print(n)
				count = 1
				break
		if count == 0:
			print(sum)
t = int(input())
for i in range(t):
	solve()


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	if b <= 10:
		r = 2 ** b
	if b >= 11:
		r = 2 ** 10
		s = 10
		while s < b and r <= a:
			r *= 3
			s += 1
	if r > a:
		r = a
	print(r)


def infect_to_ten(d):
	return 2 ** d

def infect_after_ten(d):
	return infect_to_ten(10) * 3 ** (d - 10)

def solve(*args):
	(n, d) = args
	if d > 21:
		return n
	return min(n, infect_to_ten(d) if d <= 10 else infect_after_ten(d))

def do_codechef():
	for t in range(int(input())):
		(n, d) = map(int, input().split(' '))
		print(solve(n, d))
do_codechef()
exit()


t = int(input())
for i in range(t):
	s = 1
	(n, d) = map(int, input().split())
	for i in range(1, d + 1):
		if i <= 10:
			s = 2 * s
			if s > n:
				s = n
				break
		else:
			s = 3 * s
			if s > n:
				s = n
				break
	print(s)


ujju = int(input())
for s in range(ujju):
	(v1, v2) = map(int, input().split())
	vm = 1
	if v2 <= 10:
		vm = pow(2, v2)
	elif v2 > 10 and v2 < 30:
		vm = pow(2, 10) * pow(3, v2 - 10)
	else:
		vm = v1
	if vm >= v1:
		print(v1)
	else:
		print(vm)


t = int(input())
while t:
	(n, d) = map(int, input().split(' '))
	if d <= 10:
		if 1 << d >= n:
			print(n)
		else:
			print(1 << d)
	elif d >= 32:
		print(n)
	elif pow(3, d - 10) * (1 << 10) >= n:
		print(n)
	else:
		print(pow(3, d - 10) * (1 << 10))
	t -= 1


t = int(input())
res = 0
for i in range(t):
	while t != 0:
		nd = [int(x) for x in input().split()]
		if nd[1] > 56:
			res = nd[0]
		elif nd[1] > 10:
			res = 2 ** 10 * 3 ** (nd[1] - 10)
		else:
			res = 2 ** nd[1]
		if res > nd[0]:
			print(nd[0])
		else:
			print(res)
		t -= 1


def spread(n, d):
	if d > 10:
		r = d - 10
		total = 1024
		while total < n and r > 0:
			total *= 3
			r -= 1
		return min(total, n)
	else:
		return min(2 ** d, n)
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	print(spread(n, d))


for _ in range(int(input())):
	(N, D) = map(int, input().split())
	P = 0
	if D <= 10:
		P = 2 ** D
	else:
		D -= 10
		P = 2 ** 10
		while D != 0 and P < N:
			P *= 3
			D -= 1
	print(min(N, P))


def covid_spread(population, days):
	infections = 1
	for day in range(days):
		if day < 10:
			infections *= 2
		else:
			infections *= 3
		if infections > population:
			return population
	return infections
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	print(covid_spread(n, d))


t = int(input())
for _ in range(0, t):
	inf_per = 1
	(n, d) = map(int, input().split())
	for i in range(1, d + 1):
		if i <= 10:
			inf_per *= 2
		else:
			inf_per *= 3
		if inf_per >= n:
			break
	print(min(n, inf_per))


import math
T = int(input())
for tj in range(T):
	(N, D) = map(int, input().split())
	if D <= 10:
		print(min(N, 2 ** D))
	else:
		log_n = math.log(N / 1024, 3)
		if log_n <= D - 10:
			print(N)
		else:
			print(2 ** 10 * 3 ** (D - 10))


n = int(input())
for i in range(n):
	(n1, d) = map(int, input().split())
	a = 1
	for i in range(1, d + 1):
		if i <= 10:
			a *= 2
		else:
			a *= 3
		if a >= n1:
			break
	print(min(a, n1))


import sys
input = sys.stdin.readline
for i in range(int(input())):
	(n, d) = map(int, input().split())
	c = 1
	for j in range(min(d, 10)):
		c *= 2
	for j in range(10, d):
		c *= 3
		if c >= n:
			break
	print(min(c, n))


import sys
input = sys.stdin.readline
for z in range(int(input())):
	(n, d) = map(int, input().split())
	a = 1
	for i in range(min(d, 10)):
		a *= 2
	for i in range(10, d):
		a *= 3
		if a >= n:
			break
	print(min(a, n))


def spread(N, D):
	infected = 1
	for i in range(1, D + 1):
		if i <= 10:
			infected = infected * 2
		elif infected < N:
			infected = infected * 3
		else:
			break
	if infected > N:
		return N
	else:
		return infected
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	print(spread(n, d))


num = int(input())
for num1 in range(num):
	(n, d) = map(int, input().split())
	t = 1
	i = 0
	while t < n and i <= d:
		if i in range(1, 11):
			t *= 2
		if i >= 11:
			t *= 3
		if t > n:
			t = n
		i += 1
	print(t)


for i in range(int(input())):
	final = 1
	(n, d) = map(int, input().split())
	for pqrs in range(1, d + 1):
		if pqrs <= 10:
			final = final * 2
		else:
			final = final * 3
		if final >= n:
			break
	print(min(n, final))


import sys
tokens = ''.join(sys.stdin.readlines()).split()[::-1]

def next():
	return tokens.pop()

def nextInt():
	return int(next())

def nextFloat():
	return float(next())

def getIntArray(n):
	return [nextInt() for _ in range(n)]

def getFloatArray(n):
	return [nextFloat() for _ in range(n)]

def getStringArray(n):
	return [next() for _ in range(n)]
testcase = True

def solve(testcase=1):
	(N, D) = (nextInt(), min(nextInt(), 100))
	inf = 1
	for i in range(1, D + 1):
		if i <= 10:
			inf <<= 1
		else:
			inf *= 3
	print(min(inf, N))
	pass
if testcase is None:
	testcaseCount = 1
	while tokens:
		solve(testcaseCount)
		testcaseCount += 1
else:
	testcaseCount = nextInt() if testcase else 1
	for tc in range(testcaseCount):
		solve(tc + 1)
	assert not tokens


t = int(input())
while t != 0:
	t = t - 1
	(n, d) = map(int, input().split())
	if d <= 10:
		i = 2 ** d
	else:
		i = 2 ** 10
		for k in range(11, d + 1):
			i = i * 3
			if i > n:
				break
	if i > n:
		print(n)
	else:
		print(i)


T = int(input())
for _ in range(0, T):
	per = 1
	(n, d) = map(int, input().split())
	for i in range(1, d + 1):
		if i <= 10:
			per *= 2
		else:
			per *= 3
		if per >= n:
			break
	print(min(n, per))


times = int(input())
while times != 0:
	tmp = [int(i) for i in list(input().split())]
	population = tmp[0]
	days = tmp[1]
	infected = 1
	while days != 0 and population >= infected:
		if infected >= 1024:
			infected = infected * 3
		else:
			infected = infected * 2
		days -= 1
	if population <= infected:
		print(population)
	else:
		print(infected)
	times -= 1


try:
	t = int(input())
	for i in range(0, t):
		inf = 1
		(n, d) = map(int, input().split())
		for i in range(1, d + 1):
			if i <= 10:
				inf = inf * 2
			else:
				inf = inf * 3
			if inf >= n:
				break
		print(min(n, inf))
except:
	pass


T = int(input())
for i in range(0, T):
	(N, D) = map(int, input().split())
	D1 = 1
	while D != 0 and N >= D1:
		if D <= 10:
			D1 = D1 * 2
		else:
			D1 = D1 * 3
		D -= 1
	if D1 <= N:
		print(D1)
	else:
		print(N)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
for _ in range(int(input())):
	(n, d) = list(map(int, input().split()))
	if d <= 10:
		print(min(n, l[d]))
	else:
		r = d - 10
		if log(n / 1024, 3) < r:
			print(n)
			continue
		print(min(n, 1024 * 3 ** r))


T = int(input())
if T <= 300:
	for i in range(T):
		(N, D) = map(int, input().strip().split())
		if D < 30:
			if D <= 10:
				s = 2 ** D
			elif D > 10:
				D = D - 10
				s = 1024 * 3 ** D
			if N < s:
				print(N)
			else:
				print(s)
		else:
			print(N)


T = int(input())
for i in range(T):
	(N, D) = map(int, input().split(' '))
	infected = 1
	while D != 0:
		if D > 10:
			infected = infected * 3
			D -= 1
		else:
			infected = infected * 2
			D -= 1
		if infected > N:
			break
	print(min(N, infected))