Read problem statements in [Mandarin Chinese] and [Bengali].

You are given N identical squares, each with side length A. All the squares have their sides parallel to the x-axis and y-axis. That is, the squares are not tilted. You have to take several (possibly, zero or all) squares and rearrange them to obtain a mega square. The mega square can't have any gap in the enclosed region or have overlapping squares. Also, you cannot rotate any square.

Output the side length of the largest mega square that you can obtain.

------ 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.
- The first and only line of each test case contains two space-separated integers N, A.

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

For each test case, print a single line containing one integer - the side length of the largest square you can obtain.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A ≤ 10^{4}$

----- Sample Input 1 ------ 
5
3 2
5 3
16 18
11 8
8 6

----- Sample Output 1 ------ 
2
6
72
24
12

----- explanation 1 ------ 
Test case $1$:  You can choose just one square to form the mega square. So the side length will be $2$.

Test case $2$:  You can choose $4$ squares to form a mega square with side-length $2 \cdot A$ $= 6$.

Source: codechef | Difficulty: EASY
Tags: Geometry

Mathematics


Solutions:
for i in range(int(input())):
	(a, b) = map(int, input().split())
	print(int(a ** 0.5) * b)


t = int(input())
while t > 0:
	(n, a) = map(int, input().split())
	sq = int(n ** 0.5)
	print(sq * a)
	t -= 1


for _ in range(int(input())):
	(n, a) = map(int, input().split())
	sq = int(n ** 0.5)
	print(sq * a)


for i in range(int(input())):
	(n, a) = map(int, input().split())
	p = 0
	while p * p <= n:
		p += 1
	print(a * (p - 1))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = int(a ** 0.5)
	print(s * b)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	k = 1
	for i in range(1, a // 2 + 1):
		if i ** 2 <= a:
			k = i
		else:
			break
	print(k * b)


import math
t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	ans = int(math.sqrt(n)) * a
	print(ans)


from math import *
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = int(sqrt(a)) * b
	print(c)


from math import sqrt
for i in range(int(input())):
	(n, a) = map(int, input().split())
	print(int(sqrt(n)) * a)


for i in range(int(input())):
	(n, a) = map(int, input().split())
	s = int(n ** 0.5)
	print(s * a)


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = math.sqrt(a)
	d = math.floor(c)
	print(b * d)


import math
T = int(input())
for i in range(T):
	(N, X) = map(int, input().split())
	a = math.sqrt(N)
	n = math.floor(a)
	print(n * X)


t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	print(int(pow(n, 0.5)) * a)


import math
t = int(input())
for i in range(t):
	(n, a) = map(int, input().split())
	ans = math.floor(n ** 0.5)
	print(ans * a)


for i in range(int(input())):
	(n, a) = map(int, input().split())
	c = 0
	k = n ** 0.5 + 1
	for i in range(0, int(k)):
		if i * i <= n:
			c = i
	print(c * a)


for _ in range(int(input())):
	(n, a) = map(int, input().split())
	i = 1
	j = i ** 2
	while j <= n:
		i = i + 1
		j = i ** 2
	i -= 1
	print(i * a)


import math
for t in range(int(input())):
	(n, a) = map(int, input().split(' '))
	m = int(math.sqrt(n))
	print(m * a)


import math
for _ in range(int(input())):
	(n, l) = map(int, input().split())
	print(math.floor(math.sqrt(n)) * l)


import math
p = int(input())
for i in range(p):
	(N, A) = list(map(int, input().split()))
	side_length = math.floor(math.sqrt(N))
	if p > 0:
		print(side_length * A)


for _ in range(int(input())):
	(sq, a) = map(int, input().split())
	n = 1
	while n * n <= sq:
		n += 1
	scount = n - 1
	print(scount * a)


import math
t = int(input())
while t > 0:
	(n, a) = map(int, input().split(' '))
	k = math.floor(math.sqrt(n))
	print(a * k)
	t -= 1


from math import sqrt
t = int(input())
while t > 0:
	(n, a) = map(int, input().split(' '))
	b = int(sqrt(n))
	print(b * a)
	t = t - 1


def solve():
	mul = 0
	i = 1
	while i * i <= n:
		mul = i
		i += 1
	return a * mul
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	print(solve())


import sys
for _ in range(int(sys.stdin.readline())):
	[n, a] = map(int, sys.stdin.readline().split())
	sys.stdout.write(str(int(n ** 0.5) * a) + '\n')


import math
t = int(input())
for i in range(t):
	(n, a) = map(int, input().split())
	x = int(math.sqrt(n))
	print(x * a)


t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	for i in range(1, n + 1):
		if i * i > n:
			print((i - 1) * a)
			break
		elif i * i == n:
			print(i * a)
			break


import math

def func(num):
	sr = round(math.sqrt(num), 1)
	l = str(sr).split('.')
	if l[-1] == '0':
		return num
	else:
		return func(num - 1)
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	if n < 4:
		print(a)
	else:
		print(int(func(n) ** 0.5) * a)


import math

def dtype(n):
	x = round(math.sqrt(n), 1)
	y = str(x).split('.')
	if y[-1] == '0':
		return n
	else:
		return dtype(n - 1)
t = int(input())
for i in range(t):
	(n, a) = map(int, input().split())
	if n < 4:
		print(a)
	else:
		b = dtype(n)
		print(int(math.sqrt(b)) * a)


for i in range(int(input())):
	a = [int(x) for x in input().split()]
	for j in range(1, 100000000):
		x = j * j
		if a[0] < x:
			print(a[1] * (j - 1))
			break


import math
for i in range(0, int(input())):
	(N, A) = map(int, input().split())
	n = int(math.sqrt(N))
	print(n * A)


for _ in range(int(input())):
	(n, a) = map(int, input().split())
	print(int(n ** (1 / 2)) * a)


import math
T = int(input())
for i in range(T):
	(N, A) = map(int, input().split())
	print(math.floor(math.sqrt(N)) * A)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, r) = IP()
	print(r * int(sqrt(n)))


for j in range(int(input())):
	(n, a) = map(int, input().split())
	for i in range(n + 1):
		if i * i == n:
			print(i * a)
			break
		elif i * i > n:
			print((i - 1) * a)
			break


import math
t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	x = math.floor(math.sqrt(n))
	print(a * x)


from math import sqrt
for _ in range(int(input())):
	(N, A) = map(int, input().split())
	x = int(sqrt(N))
	print(x * A)


for _ in range(int(input())):
	(n, a) = map(int, input().split())
	count1 = 1
	pre = 1
	count2 = 1
	u = 0
	if n == 0:
		print(0)
	else:
		while count1 != 0:
			count = count2
			v = pre + 2
			pre = v
			count2 += v
			if n >= count:
				count = count2
				u += 1
			else:
				count1 = 0
	print(a * u)


t = int(input())
while t:
	(n, x) = map(int, input().split())
	print(int(n ** (1 / 2)) * x)
	t -= 1


from math import sqrt
t = int(input())
while t:
	(n, x) = map(int, input().split())
	print(int(sqrt(n)) * x)
	t -= 1


for t in range(int(input())):
	(n, a) = list(map(int, input().split()))
	b = int(n ** 0.5)
	print(a * b)


for _ in range(int(input())):
	(N, A) = map(int, input().split())
	print(int(N ** 0.5) * A)


import math
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	if n < 4:
		print(a)
	else:
		c = math.floor(math.sqrt(n))
		print(c * a)


from math import sqrt
n = int(input())
for i in range(n):
	(a, b) = list(map(int, input().split()))
	c = int(sqrt(a))
	print(c * b)


from math import sqrt
t = int(input())
for i in range(t):
	(N, A) = map(int, input().split())
	B = int(sqrt(N))
	print(B * A)


import math
t = int(input())
while t > 0:
	x = input().split(' ')
	n = int(x[0])
	a = int(x[1])
	temp = math.sqrt(n) // 1
	print(int(temp * a))
	t = t - 1


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = math.floor(a ** 0.5)
	print(x * b)


import math
for T in range(int(input())):
	(n, a) = map(int, input().split())
	print(math.floor(math.sqrt(n)) * a)


import math
for o in range(int(input())):
	(n, a) = list(map(int, input().split()))
	sqrtN = int(math.sqrt(n))
	print(sqrtN * a)


for _ in range(int(input())):
	(N, A) = map(int, input().split())
	max = 1
	for i in range(1, N + 1):
		if i * i > max and i * i <= N:
			max = i
	print(A * max)


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	k = math.floor(math.sqrt(a))
	print(k * b)