Roy lives in a city that is circular in shape on a $2{D}$ plane that has radius ${r}$. The city center is located at origin $(0,0)$ and it has suburbs lying on the lattice points (points with integer coordinates). The city Police Department Headquarters can only protect those suburbs which are located strictly inside the city. The suburbs located on the border of the city are still unprotected. So the police department decides to build at most ${k}}$ additional police stations at some suburbs. Each of these police stations can protect the suburb it is located in.

Given the square of radius, $d(=r^2)$, of the city, Roy has to determine if it is possible to protect all the suburbs.

Input Format 

The first line of input contains integer ${t}}$; ${t}}$ test cases follow. 

Each of the next ${t}}$ lines contains two space-separated integers: ${d}$, the square of the radius of the city, and ${k}$, the maximum number of police stations the headquarters is willing to build.

Constraints 

$1\leq t\leq10^3$ 

$1\leq d\leq2\times10^9$ 

$0\leq k\leq2\times10^9$  

Output Format 

For each test case, print in a new line possible if it is possible to protect all the suburbs;, otherwise, print impossible.

Sample Input

5
1 3
1 4
4 4
25 11
25 12

Sample Output

impossible
possible
possible
impossible
possible

Explanation  

For ${d}=1$, there are ${4}$ points on circumference - [(0,1), (0,-1), (1,0), (-1,0)].
For ${d}=4$, there are ${4}$ points on circumference - [(0,2), (0,-2), (2,0),(-2,0)].
For ${d}=25$, there are $12$ points on circumference - [(0,5), (0,-5), (3,4), (-3,4), (3,-4), (-3,-4), (4,3), (-4,3), (4,-3), (-4,-3), (5,0), (-5,0)].

Test Case #01: There are ${4}$ suburbs on the border, while we are allowed to construct max $k=3$ police stations. 

Test Case #02: We can cover all the ${4}$ suburbs as exactly ${4}$ stations are allowed. 

Test Case #03: We can cover all the ${4}$ suburbs as exactly ${4}$ stations are allowed. 

Test Case #04: It is impossible to cover $12$ suburbs, on the border, with ${11}$ police stations. 

Test Case #05: We can to cover all $12$ suburbs, on the border, with $12$ police stations.  

Timelimits  

Timelimits for this challenge are given here

Source: hackerrank | Difficulty: MEDIUM
Tags: Geometry


Solutions:
import math

def need(r):
	ret = 0
	if r % 2 == 0 and int(math.sqrt(r // 2)) ** 2 == r // 2:
		ret += 4
	y = int(math.sqrt(r))
	if y * y == r:
		ret += 4
	x = 1
	while True:
		while x < y and x * x + y * y > r:
			y -= 1
		if x >= y:
			break
		if x * x + y * y == r:
			ret += 8
		x += 1
	return ret
t = int(input())
for _ in range(t):
	(r, k) = map(int, input().split())
	print('possible' if k >= need(r) else 'impossible')


import math

def f(r, k):
	res = 0
	for i in range(math.ceil(math.sqrt(r))):
		b = math.sqrt(r - i * i)
		if b == int(b):
			res += 1
	res *= 4
	if res <= k:
		return 'possible'
	return 'impossible'
for case_t in range(int(input())):
	(r, k) = [int(i) for i in input().strip().split(' ')]
	print(f(r, k))


from math import sqrt, ceil, floor
for t in range(int(input())):
	(r, k) = [int(i) for i in input().split()]
	sqrt_half_r = ceil(sqrt(r / 2))
	count = 0
	for x in range(1, sqrt_half_r):
		x_2 = x * x
		y_2 = r - x_2
		if floor(sqrt(y_2)) == ceil(sqrt(y_2)):
			count += 1
	count *= 2
	if floor(sqrt(r / 2)) == ceil(sqrt(r / 2)):
		count += 1
	count *= 4
	if floor(sqrt(r)) == ceil(sqrt(r)):
		count += 4
	if count <= k:
		print('possible')
	else:
		print('impossible')


import sys, math
for i in range(int(sys.stdin.readline())):
	a = list(map(float, str(input()).split()))
	c = math.sqrt(a[0])
	d = math.sqrt(2)
	if 2 * c ** 2 >= a[1]:
		if c % 1 == 0:
			if a[1] >= 4:
				b = len([1 for i in range(int(c) - 1, int(c / d), -1) if math.sqrt(a[0] - i ** 2) % 1 == 0]) * 8 + 4
				if b > a[1]:
					print('impossible')
				else:
					print('possible')
			else:
				print('impossible')
		else:
			b = len([1 for i in range(int(c) + 1) if math.sqrt(a[0] - i ** 2) % 1 == 0]) * 4
			if b > a[1]:
				print('impossible')
			else:
				print('possible')
	elif a[0] == 1:
		if 4 > a[1]:
			print('impossible')
		else:
			print('possible')
	else:
		print('possible')


import math
squares = set()
for i in range(44722):
	squares.add(i * i)
for i in range(int(input())):
	count = 0
	arr = [int(j) for j in input().split()]
	for j in range(1, int(math.sqrt(arr[0])) + 1):
		if arr[0] - j * j in squares:
			count = count + 1
	if count * 4 > arr[1]:
		print('impossible')
	else:
		print('possible')


from math import sqrt
testcases = int(input())
for i in range(testcases):
	(radius2, stations) = [int(i) for i in input().split()]
	x = 1
	y = sqrt(radius2)
	total = 0
	first_quad = 0
	radius = y
	if y - int(y) == 0:
		total += 4
	y = int(y)
	while x < radius and x <= y and (total <= stations):
		temp = x * x + y * y
		if temp == radius2:
			if x == y:
				total += 4
			else:
				total += 8
			y -= 1
		elif temp > radius2:
			y -= 1
		x += 1
	if total > stations:
		print('impossible')
	else:
		print('possible')


get_int = lambda : int(input())
get_list = lambda : [int(s) for s in input().split()]
from math import sqrt, ceil, floor
squares = {i * i for i in range(floor(sqrt(4000000000.0) + 1))}
for _ in range(get_int()):
	(rr, k) = get_list()
	r = floor(sqrt(rr) + 1)
	cnt = sum((4 for a in range(1, r) if rr - a * a in squares))
	print('impossible' if cnt > k else 'possible')


test_cases = int(input())
for i in range(test_cases):
	(r_squared, k) = map(int, input().split(' '))
	r = int(r_squared ** 0.5)
	count = 0
	for x in range(1, r + 1):
		if (r_squared - x * x) ** 0.5 % 1 == 0:
			count += 4
	if count <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt, ceil, modf
t = int(input())
for _ in range(t):
	point = 0
	(r, k) = map(int, input().split())
	for x in range(ceil(sqrt(r))):
		y = sqrt(r - x * x)
		if modf(y)[0] == 0:
			point += 4
	if point <= k:
		print('possible')
	else:
		print('impossible')


import itertools
import math
import numbers
import sys
MAX_R = 2 * 1000000000.0
PERFECT_SQUARES = set()
for x in range(int(math.ceil(math.sqrt(MAX_R)))):
	square = pow(x, 2)
	PERFECT_SQUARES.add(square)

def is_perfect_square(x):
	return x in PERFECT_SQUARES

def get_y(rsquare, x):
	return math.sqrt()

def nlattice_points(rsquare):
	total = 0
	for x in range(0, int(math.ceil(math.sqrt(rsquare)))):
		y = rsquare - pow(x, 2)
		if is_perfect_square(y):
			total += 1
	return total * 4

def can_protect_city(rsquare, nstations):
	required_stations = nlattice_points(rsquare)
	return nstations >= required_stations
ncases = int(sys.stdin.readline())
for case_index in range(ncases):
	(rsquare, nstations) = [int(x) for x in sys.stdin.readline().split()]
	if can_protect_city(rsquare, nstations):
		print('possible')
	else:
		print('impossible')


from math import sqrt, sin, floor
cache = {}

def points_on_margin(dist_2):
	if dist_2 in cache:
		return cache[dist_2]
	dist = round(sqrt(dist_2))
	res = 0
	if dist ** 2 == dist_2:
		res += 4
	if round(sqrt(dist_2 / 2)) ** 2 * 2 == dist_2:
		res += 4
		top = round(sqrt(dist_2 / 2)) - 1
	else:
		top = round(sqrt(dist_2 / 2))
		while top > round(sqrt(dist_2 - top ** 2)):
			top -= 1
	for row in range(1, top + 1):
		col = sqrt(dist_2 - row * row)
		if col == int(col):
			res += 8
	cache[dist_2] = res
	return res
for _ in range(int(input())):
	(r, k) = [int(s) for s in input().split()]
	if points_on_margin(r) > k:
		print('impossible')
	else:
		print('possible')


from math import floor, sqrt

def stationsNeeded(squareOfRadius):
	result = 0
	for i in range(1, floor(sqrt(squareOfRadius)) + 1):
		if sqrt(squareOfRadius - i ** 2).is_integer():
			result += 4
	return result
for _ in range(int(input())):
	(squareOfRadius, maxStations) = (int(x) for x in input().split(' '))
	needed = stationsNeeded(squareOfRadius)
	print('possible' if needed <= maxStations else 'impossible')


squares = [1]
sq = 1
while sq ** 2 < 10 ** 12:
	squares += [sq ** 2]
	sq += 1
T = int(input())
for t in range(0, T):
	line = [int(z) for z in input().split()]
	N = line[0]
	k = line[1]
	i = 0
	res = 0
	while squares[i] <= N / 2:
		if ((N - squares[i]) ** 0.5).is_integer():
			res += 1
		i += 1
	treba = res * 4 * 2
	if (N ** 0.5).is_integer():
		treba += 4
	if k - treba >= 0:
		print('possible')
	else:
		print('impossible')


from math import sqrt
for _ in range(int(input())):
	(r, k) = map(int, input().split())
	if k >= sum((4 for i in range(1, int(sqrt(r) + 1)) if sqrt(r - i * i) % 1 == 0)):
		print('possible')
	else:
		print('impossible')


import math
t = int(input())
for ti in range(t):
	(r, k) = map(int, input().split(' '))
	upper = math.ceil(math.sqrt(r) * math.pi / 4)
	y = math.floor(math.sqrt(r))
	subs = 0
	if y * y == r or (y + 1) * (y + 1) == r:
		subs += 4
	for x in range(1, upper + 1):
		tr = x * x + y * y
		if tr > r and y > 1:
			y -= 1
			tr = x * x + y * y
		if tr == r:
			subs += 8
	if subs > k:
		print('impossible')
	else:
		print('possible')


import math
t = int(input())

def count_coverage(r, k):
	count = 0
	for i in range(math.ceil(math.sqrt(r))):
		if math.sqrt(r - math.pow(i, 2)).is_integer():
			count += 4
	if k >= count:
		print('possible')
	else:
		print('impossible')
for i in range(t):
	row = [int(x) for x in input().split()]
	count_coverage(row[0], row[1])


import math

def generatePoints(r):
	a = 0
	squares = []
	squares_d = {}
	for i in range(int(math.sqrt(r)) + 1):
		ii = i * i
		squares.append(ii)
		squares_d[ii] = 1
	for x in squares:
		if x == 0:
			continue
		y = r - x
		if y in squares_d:
			a += 1
	return a * 4
t = int(input())
for test in range(t):
	(r, k) = [int(x) for x in input().split()]
	if generatePoints(r) <= k:
		print('possible')
	else:
		print('impossible')


sq = set((i * i for i in range(100000)))
for _ in range(int(input())):
	(r, k) = [int(i) for i in input().split()]
	x = 0
	ct = 0
	while x * x < r:
		if r - x * x in sq:
			ct += 1
		x += 1
	print('possible' if k >= 4 * ct else 'impossible')


import math
for _ in range(int(input())):
	(r_sqrd, k) = [int(i) for i in input().split()]
	for x in range(1, int(math.sqrt(r_sqrd)) + 1):
		if math.sqrt(r_sqrd - x * x) % 1 == 0:
			k -= 4
			if k < 0:
				break
	print('possible' if k >= 0 else 'impossible')


import math

def count_on(r):
	k = math.sqrt(r)
	c = 0
	for i in range(int(k), 0, -1):
		if math.sqrt(r - i * i).is_integer():
			c = c + 1
	return 4 * c
t = int(input())
ar = []
for i in range(t):
	ar.append([])
	ar[i] = input().split()
for i in range(t):
	r = count_on(int(ar[i][0]))
	if r > int(ar[i][1]):
		print('impossible')
	else:
		print('possible')


t = int(input())
p = {i ** 2 for i in range(44722)}
for i in range(t):
	(r, k) = map(int, input().split())
	c = p & {r - v for v in p}
	n = 0
	if 0 in c:
		c -= {0, r}
		n += 4
	if r // 2 in c:
		c -= {r // 2}
		n += 4
	n += 4 * len(c)
	print('possible' if n <= k else 'impossible')


import math

def canProtectAllSuburbs(maximumNumberOfStations, numberOfSuburbs):
	if maximumNumberOfStations >= numberOfSuburbs:
		return True
	else:
		return False

def r2(rSquared, squares):
	result = 0
	for i in range(0, rSquared + 1):
		jSquared = rSquared - i ** 2
		if jSquared < 0:
			break
		if jSquared in squares:
			if i == 0 or squares[jSquared] == 0:
				result += 2
			else:
				result += 4
	return result
numTestCases = int(input())
squares = {x ** 2: x for x in range(0, 50001)}
for i in range(0, numTestCases):
	line = list(map(int, input().split(' ')))
	rSquared = line[0]
	maximumNumberOfStations = line[1]
	suburbs = r2(rSquared, squares)
	if canProtectAllSuburbs(maximumNumberOfStations, suburbs):
		print('possible')
	else:
		print('impossible')


from math import floor, ceil, sqrt

def isInt(x):
	return floor(x) == ceil(x)
numTests = int(input())
for test in range(numTests):
	(rSquared, numAvailable) = [int(n) for n in input().split(' ')]
	numPoints = 0
	for x in range(1, ceil(sqrt(rSquared / 2))):
		if isInt(sqrt(rSquared - x ** 2)):
			numPoints += 8
	if isInt(sqrt(rSquared)):
		numPoints += 4
	elif isInt(sqrt(rSquared / 2)):
		numPoints += 4
	if numPoints <= numAvailable:
		print('possible')
	else:
		print('impossible')


def binarySearch(alist, item):
	first = 0
	last = len(alist) - 1
	found = False
	while first <= last and (not found):
		midpoint = (first + last) // 2
		if alist[midpoint] == item:
			return midpoint
		elif item < alist[midpoint]:
			last = midpoint - 1
		else:
			first = midpoint + 1
	return first
squares = []
base = 0
square = 0
while square <= 2000000000:
	squares.append(square)
	base += 1
	square = base ** 2
T = int(input())
for tc in range(T):
	rk = input().split()
	r = int(rk[0])
	k = int(rk[1])
	n = 0
	small = 0
	large = min(binarySearch(squares, r) + 1, len(squares) - 1)
	while large >= small:
		s = squares[large] + squares[small]
		if s > r:
			large -= 1
		elif s < r:
			small += 1
		else:
			n += 4
			if small != 0 and large != small:
				n += 4
			if n > k:
				break
			large -= 1
	if n <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt, ceil

def f(r):
	ret = 0
	for x in range(0, ceil(sqrt(r))):
		y = int(sqrt(r - x * x))
		if x * x + y * y == r:
			ret += 4
	return ret
t = int(input())
for _ in range(t):
	(r, k) = [int(v) for v in input().split()]
	total = f(r)
	if total <= k:
		print('possible')
	else:
		print('impossible')


import math
t = int(input())
while t > 0:
	(d, k) = input().split()
	d = int(d)
	k = int(k)
	r = int(math.sqrt(d))
	suburbs = 0
	r = math.sqrt(d)
	if r == int(r):
		suburbs += 4
	else:
		r += 1
	r = int(r)
	for x in range(1, r):
		y = math.sqrt(d - x * x)
		if y == int(y):
			suburbs += 4
	print('possible' if suburbs <= k else 'impossible')
	t -= 1


import math
n = int(input())

def getSuburbs(d):
	num = 0
	r = math.sqrt(d)
	m = int(r)
	if r != m:
		m = m + 1
	for i in range(0, m):
		j = math.sqrt(d - i * i)
		if j == int(j):
			num += 4
	return num
for i in range(n):
	s = [int(i) for i in input().split()]
	d = s[0]
	sub = s[1]
	if getSuburbs(d) <= sub:
		print('possible')
	else:
		print('impossible')


from math import ceil, sqrt

def parse_case(D, K):
	count = 0
	for i in range(ceil(sqrt(D))):
		j = sqrt(D - i ** 2)
		if j.is_integer():
			count += 1
	if count * 4 <= K:
		return 'possible'
	else:
		return 'impossible'
T = int(input())
for _ in range(T):
	(D, K) = [int(c) for c in input().strip().split()]
	print(parse_case(D, K))


from math import sqrt
t = int(input())
for _ in range(t):
	d = input().split()
	r = int(d[0])
	k = int(d[1])
	N = int(sqrt(r))
	a = {r - i * i for i in range(1, N + 1)}
	b = {i * i for i in range(1, N + 1)}
	elements = a.intersection(b)
	count = len(list(elements))
	count = count * 4
	if sqrt(r) % 1 == 0:
		count += 4
	if count > k:
		print('impossible')
	else:
		print('possible')


import math
n = lambda : int(input())
ns = lambda : list(map(int, input().split()))
DEBUG = 0

def int_borders(d, maxcalc):
	ret = []
	r = math.ceil(d ** 0.5)
	if r * 4 < maxcalc:
		return []
	for c1 in range(r):
		c2 = (d - c1 ** 2) ** 0.5
		if DEBUG:
			print('locals=', repr(locals()))
		if math.floor(c2) == c2:
			ret.append((c1, c2))
	return ret
T = n()
for _ in range(T):
	(d, k) = ns()
	borders = int_borders(d, k)
	if DEBUG:
		print(repr(borders))
	if len(borders) * 4 > k:
		print('impossible')
	else:
		print('possible')


from math import sqrt

def isPerfect(n):
	sqroot = int(sqrt(n))
	if sqroot * sqroot == n:
		return True
	else:
		return False
T = int(input())
for _ in range(T):
	(d, k) = (int(x) for x in input().split())
	r = int(sqrt(d))
	TotalPoints = 0
	for Cor in range(1, r + 1):
		if isPerfect(d - Cor * Cor):
			TotalPoints += 4
	if TotalPoints <= k:
		print('possible')
	else:
		print('impossible')


from operator import mul
from functools import reduce
from itertools import groupby

def td_factors(n, limit=1000000000):
	fs = []
	while not n % 2:
		fs.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if limit < f:
			raise OverflowError('limit exceeded')
		while not n % f:
			fs.append(f)
			n //= f
		f += 2
	return fs if n == 1 else fs + [int(n)]

def A046080(n):
	p = reduce(mul, (sum((2 for gi in g)) + 1 for (k, g) in groupby(td_factors(n)) if k % 4 == 1), 1)
	return 4 * p

def A004018(n):
	f = [(sum((1 for gi in g)), k) for (k, g) in groupby(td_factors(n))]
	if any((pf & 1 for (pf, p) in f if p % 4 == 3)):
		return 0
	return 4 * reduce(mul, (pf + 1 for (pf, p) in f if p % 4 == 1), 1)

def city(dsq, n):
	counts = A004018(dsq)
	return 'possible' if counts <= n else 'impossible'
T = int(input())
for case in range(T):
	(d2, n) = map(int, input().split())
	print(city(d2, n))


from math import sqrt
from math import ceil

def isSquare(x):
	return sqrt(x).is_integer()
t = int(input())
for _ in range(t):
	(d, k) = list(map(int, input().split()))
	res = 0
	s = int(ceil(sqrt(d)))
	ok = True
	for x in range(s):
		if isSquare(d - x ** 2):
			res += 4
		if res > k:
			ok = False
			break
	print('possible' if ok else 'impossible')


def is_square(n):
	temp = pow(n, 0.5)
	if temp - int(temp) == 0:
		return True
	else:
		return False

def fun(d, k):
	total = 0
	temp = int(pow(d / 2, 0.5))
	for i in range(temp + 1):
		if is_square(d - i * i):
			if i == 0 or 2 * (i * i) == d:
				total += 4
			else:
				total += 8
	if total <= k:
		return True
	else:
		return False
t = int(input())
while t:
	t -= 1
	(d, k) = [int(i) for i in input().split()]
	if fun(d, k):
		print('possible')
	else:
		print('impossible')


import math

def circleLattice(d):
	count = 0
	for i in range(1, math.ceil(math.sqrt(d))):
		if math.sqrt(d - i * i) % 1 == 0:
			count += 1
	if math.sqrt(d) % 1 == 0:
		return 4 * count + 4
	elif count != 0:
		return 4 * count
	else:
		return 0
for _ in range(int(input())):
	(d, k) = [int(num) for num in input().split()]
	if circleLattice(d) <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt
for _ in range(int(input())):
	(d, k) = map(int, input().split(' '))
	(c, s) = (0, int(sqrt(d)))
	for i in range(1, s + 1):
		q = d - i * i
		n = int(sqrt(q))
		if q == 0 or n * n == q:
			c += 4
	print('possible' if c <= k else 'impossible')


import math

def f(r, k):
	res = 0
	for i in range(math.ceil(math.sqrt(r))):
		b = math.sqrt(r - i * i)
		if b == int(b):
			res += 1
	res *= 4
	if res <= k:
		return 'possible'
	return 'impossible'
for case_t in range(int(input())):
	(r, k) = [int(i) for i in input().strip().split(' ')]
	print(f(r, k))


from math import sqrt, ceil
T = int(input())
for _ in range(T):
	(D, K) = list(map(int, input().split(' ')))
	total = 0
	stop = int(ceil(sqrt(D)))
	for x in range(stop):
		if sqrt(D - x ** 2).is_integer():
			total += 4
	if total <= K:
		print('possible')
	else:
		print('impossible')


from math import sqrt

def perfectSquare(x):
	y = int(sqrt(x))
	if y * y == x:
		return True
	return False
for _ in range(int(input())):
	(d, k) = list(map(int, input().split()))
	ans = 0
	n = int(sqrt(d)) if perfectSquare(d) == True else int(sqrt(d)) + 1
	for x in range(n):
		y = d - x * x
		if perfectSquare(y) == True:
			ans += 4
	if k >= ans:
		print('possible')
	else:
		print('impossible')


from math import sqrt
import sys
t = int(input().strip())
for _ in range(t):
	(d, k) = map(int, input().strip().split(' '))
	count = 0
	x = 0
	while x < sqrt(d):
		if sqrt(d - x * x).is_integer():
			count += 4
		x += 1
	if count <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt
t = int(input())

def is_in_circle(point, r):
	(x, y) = point
	if x ** 2 + y ** 2 < r:
		return True
	else:
		return False

def circunference_integers(r):
	points = set()
	skip = set()
	for x in range(int(sqrt(r)) + 1):
		if x in skip:
			continue
		y = sqrt(r - x ** 2)
		if y % 1 == 0:
			points.add((x, int(y)))
			points.add((-x, int(y)))
			points.add((x, -int(y)))
			points.add((-x, -int(y)))
			points.add((int(y), x))
			points.add((-int(y), x))
			points.add((int(y), -x))
			points.add((-int(y), -x))
			skip.add(int(y))
	return points
for a0 in range(t):
	(r, k) = [int(x) for x in input().split(' ')]
	if k >= len(circunference_integers(r)):
		print('possible')
	else:
		print('impossible')


import sys
import math
t = int(input().strip())
for i in range(t):
	n = input().strip().split(' ')
	x = int(n[0])
	y = int(n[1])
	flag = 0
	if 4 * x < y:
		print('possible')
		flag = 1
	if flag == 0:
		count = 0
		l = math.ceil(x ** 0.5)
		for j in range(0, l):
			f = (x - j * j) ** 0.5
			if f - int(f) == 0:
				count += 1
		if 4 * count <= y:
			print('possible')
		else:
			print('impossible')


lim = 44722
mark = bytearray(lim >> 1)
primes = []
for i in range(3, lim, 2):
	if mark[i >> 1] == 0:
		primes.append(i)
		for j in range(3 * i, lim, 2 * i):
			mark[j >> 1] = 1

def squares_r2(n):
	while n & 1 == 0:
		n >>= 1
	b = 4
	for p in primes:
		if n % p == 0:
			n //= p
			c = 1
			while n % p == 0:
				n //= p
				c += 1
			if p & 2 == 0:
				b *= c + 1
			elif c & 1 != 0:
				return 0
	if n == 1:
		return b
	elif n & 2 == 0:
		return 2 * b
	else:
		return 0
t = int(input())
for case in range(t):
	line = input().split()
	d = int(line[0])
	k = int(line[1])
	b = squares_r2(d)
	if k >= b:
		print('possible')
	else:
		print('impossible')


from math import sqrt, ceil, modf
for _ in range(int(input())):
	p = 0
	(d, k) = map(int, input().split())
	for x in range(ceil(sqrt(d))):
		y = sqrt(d - x * x)
		if modf(y)[0] == 0:
			p += 4
	if p > k:
		print('impossible')
	else:
		print('possible')


T = int(input())
for t in range(T):
	(d, k) = map(int, input().split())
	counter = 0
	dd = d ** 0.5
	bb = int(dd)
	S = set()
	for a in range(1, bb + 1):
		S.add(a ** 2)
	for aa in S:
		counter += d - aa in S
	counter *= 4
	if dd == bb:
		counter += 4
	if k >= counter:
		print('possible')
	else:
		print('impossible')


import math
for _ in range(int(input())):
	(d, k) = map(int, input().split())
	r = math.sqrt(d)
	count = 0
	for x in range(1, math.floor(r) + 1):
		y = math.sqrt(d - x ** 2)
		if y % 1 == 0:
			count += 4
	if count <= k:
		print('possible')
	else:
		print('impossible')


import sys
import math

def possible(d, k):
	count = 0
	i = 0
	j = int(math.sqrt(d)) + 1
	while True:
		i_sq = i * i
		while True:
			x = i_sq + j * j
			if x <= d:
				break
			j -= 1
			if j == 0:
				return True
		if x == d:
			count += 4
			if count > k:
				return False
		i += 1
tc_len = int(sys.stdin.readline())
for tc in range(tc_len):
	(d, k) = tuple((int(x) for x in sys.stdin.readline().split()))
	if possible(d, k):
		print('possible')
	else:
		print('impossible')


import math

def read_ints():
	return [int(x) for x in input().strip().split(' ')]

def read_int():
	return int(input().strip())

def compute_minimum_required(r):
	mr = 0
	st = int(math.sqrt(r // 2)) ** 2 == r // 2
	if r % 2 == 0 and st:
		mr += 4
	y = int(math.sqrt(r))
	if y * y == r:
		mr += 4
	x = 1
	while True:
		while x < y and x * x + y * y > r:
			y -= 1
		if x >= y:
			break
		if x * x + y * y == r:
			mr += 8
		x += 1
	return mr
T = read_int()
for t in range(T):
	(r, k) = read_ints()
	minimum_required = compute_minimum_required(r)
	if k >= minimum_required:
		print('possible')
	else:
		print('impossible')


import sys

def primes_gen(n):
	cache = [True] * n
	cache[0] = False
	cache[1] = False
	for i in range(n):
		if cache[i]:
			yield i
			for j in range(i + i, n, i):
				cache[j] = False

def solve(d, pcache):
	print('d=%d=1' % d, end='', file=sys.stderr)
	r = 1
	for p in pcache:
		if d < p:
			break
		pwr = 0
		while d % p == 0:
			d //= p
			pwr += 1
		if pwr:
			print('*%d^%d' % (p, pwr), end='', file=sys.stderr)
		if p % 4 == 3 and pwr % 2:
			return 0
		if p % 4 == 1:
			r *= pwr + 1
	print(file=sys.stderr)
	print('d=%d r=%d' % (d, r), file=sys.stderr)
	if d % 4 == 3:
		return 0
	if d > 1 and d % 4 == 1:
		r *= 2
	return 4 * r
pcache = [p for p in primes_gen(int(pow(2 * pow(10, 9), 0.5)) + 1)]
print('pcache: %d' % len(pcache), file=sys.stderr)
t = int(input())
for _ in range(t):
	(d, k) = map(int, input().split())
	if solve(d, pcache) <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


from math import ceil
from math import sqrt
t = int(input())
for i in range(t):
	s = input().split(' ')
	d = int(s[0])
	k = int(s[1])
	requiredPoliceStations = 0
	r = sqrt(d)
	if r == int(r):
		requiredPoliceStations += 4
	h = sqrt(d / 2)
	if h == int(h):
		requiredPoliceStations += 4
	for a in range(1, ceil(h)):
		b = sqrt(d - a * a)
		if b == int(b):
			requiredPoliceStations += 8
	print('possible' if requiredPoliceStations <= k else 'impossible')


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


import math
n = int(input())
while n > 0:
	a = input().split()
	b = int(a[1])
	a = int(a[0])
	point = 0
	l = list(map(lambda x: pow(x, 2), range(1, int(math.sqrt(a)) + 1)))
	if math.sqrt(a) - int(math.sqrt(a)) == 0.0:
		l = l[0:-1]
		point = 4
	if math.sqrt(a) - int(math.sqrt(a)) == 0.0:
		point = 4
	if len(list(set(l) & set(list(map(lambda x: a - x, l))))) * 4 + point <= b:
		print('possible')
	else:
		print('impossible')
	n = n - 1


import math

def get_num_suburbs(square_radius):
	num = 0
	for i in range(0, int(math.sqrt(square_radius)) + 1):
		b = math.sqrt(abs(i ** 2 - square_radius))
		if b.is_integer() and b <= i:
			if i == 0 or b == 0:
				num += 4
			else:
				num += 8
	return num
num_cities = int(input().strip())
for x in range(0, num_cities):
	in_array = [int(tmp.strip()) for tmp in input().split(' ')]
	square_radius = in_array[0]
	stations = in_array[1]
	if stations >= get_num_suburbs(square_radius):
		print('possible')
	else:
		print('impossible')


import math
t = int(input())
for i in range(t):
	(d, k) = [int(x) for x in input().split()]
	count = 0
	r = math.sqrt(d)
	if r.is_integer():
		count += 4
		J = int(r)
	else:
		J = int(r) + 1
	for x in range(1, J):
		y = math.sqrt(d - x * x)
		if y.is_integer():
			count += 4
	if k >= count:
		print('possible')
	else:
		print('impossible')


import math
t = int(input())
cases = []
for case in range(t):
	params = input().split()
	d = int(params[0])
	k = int(params[1])
	r = math.floor(math.sqrt(d))
	numSuburbs = 0
	y = r
	x = 0
	while y > 0:
		if math.sqrt(d - y ** 2) % 1 == 0:
			numSuburbs = numSuburbs + 1
		y = y - 1
	numSuburbs = numSuburbs * 4
	if numSuburbs > k:
		print('impossible')
	else:
		print('possible')


import math
for _ in range(int(input().strip())):
	(D, K) = map(int, input().strip().split())
	sum = 0
	for i in range(int(math.sqrt(D)) + 1):
		if math.sqrt(D - i ** 2) % 1 == 0:
			if i == 0 or math.sqrt(D - i ** 2) == 0:
				sum += 2
			else:
				sum += 4
	if sum > K:
		print('impossible')
	else:
		print('possible')


from math import sqrt, ceil
t = int(input())
for i in range(t):
	(d, k) = (int(j) for j in input().split())
	r = sqrt(d)
	res = 0
	for j in range(ceil(r)):
		b = sqrt(d - j ** 2)
		if b == int(b):
			res += 4
	if res > k:
		print('impossible')
	else:
		print('possible')


from math import *
t = int(input())
for test in range(t):
	(d, k) = map(int, input().split(' '))
	r = sqrt(d)
	q1_burbs = 0
	for x in range(ceil(r)):
		y = sqrt(d - x ** 2)
		if y == int(y):
			q1_burbs += 1
	burbs = q1_burbs * 4
	if burbs <= k:
		print('possible')
	else:
		print('impossible')


import math
numTests = int(input())
for _ in range(numTests):
	(d, k) = map(int, input().split())
	r = math.sqrt(d)
	count = 0
	for x in range(1, int(r) + 1):
		y = math.sqrt(d - x * x)
		if y == int(y):
			count += 1
	count *= 4
	if k < count:
		print('impossible')
	else:
		print('possible')


from math import sqrt
t = int(input())
case = [[int(n) for n in input().split()] for i in range(t)]
for (d, k) in case:
	suburbs = 4 if sqrt(d / 2) % 1 == 0 else 0
	b = 2 - d % 2
	while b ** 2 < d:
		if sqrt(2 * d - b ** 2) % 2 == d % 2:
			suburbs += 8
		b += 2
	if sqrt(d) % 1 == 0:
		suburbs += 4
	if suburbs <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt
for _ in range(int(input())):
	(d, k) = map(int, input().split())
	s = set((i * i for i in range(int(sqrt(d) + 1.001))))
	c = 0
	for a in s:
		b = d - a
		if a <= b and b in s:
			if a == 0 or a == b:
				c += 4
			else:
				c += 8
	print(['', 'im'][c > k] + 'possible')


def divexps(n):
	exp1 = []
	exp3 = []
	while n % 2 == 0:
		n //= 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		e = 0
		while n % i == 0:
			n //= i
			e += 1
		if i % 4 == 1:
			exp1.append(e)
		else:
			exp3.append(e)
	if n > 1:
		if n % 4 == 1:
			exp1.append(1)
		else:
			exp3.append(1)
	return (exp1, exp3)
for _ in range(int(input())):
	(d, k) = [int(a) for a in input().split()]
	(exp1, exp3) = divexps(d)
	if any((x & 1 for x in exp3)):
		count = 0
	else:
		count = 4
		for i in exp1:
			count *= i + 1
	if k < count:
		print('impossible')
	else:
		print('possible')


import math
t = int(input())
for _ in range(t):
	[d2, k] = [int(x) for x in input().strip().split(' ')]
	(i, ret) = (0, 0)
	while i * i <= d2 // 2:
		b = math.sqrt(d2 - i * i)
		if abs(b - int(b)) < 1e-06:
			if i == 0:
				ret += 4
			else:
				ret += 8
		i += 1
	if k >= ret:
		print('possible')
	else:
		print('impossible')


import math
queries = int(input())
for q in range(queries):
	counter = 0
	(d, k) = input().strip().split()
	(d, k) = [int(d), int(k)]
	for i in range(0, int(math.ceil(math.sqrt(d)))):
		j = math.sqrt(d - i * i)
		if j.is_integer():
			counter += 4
	if counter <= k:
		print('possible')
	else:
		print('impossible')


import math

def factor(d):
	primeList = []
	p = 2
	count = 0
	lim = int(math.sqrt(d))
	while d > 1:
		if d % p == 0:
			count = count + 1
			d //= p
			lim = int(math.sqrt(d))
		else:
			if count > 0:
				primeList += [(p, count)]
				count = 0
			if p == 2:
				p = 3
			else:
				p += 2
			if p > lim:
				p = d
				count = 1
				break
	if count > 0:
		primeList += [(p, count)]
	return primeList

def countCirclePointsFast(d):
	while d % 2 == 0:
		d //= 2
	primeList = factor(d)
	pointCount = 1
	for (p, count) in primeList:
		if p % 4 == 1:
			pointCount *= count + 1
		elif count % 2 == 1:
			pointCount = 0
	return 4 * pointCount
ctest = int(input())
for itest in range(ctest):
	tokens = input().split()
	d = int(tokens[0])
	k = int(tokens[1])
	if countCirclePointsFast(d) > k:
		print('impossible')
	else:
		print('possible')


T = int(input())
for t in range(T):
	(d, k) = [int(c) for c in input().split(' ')]
	squares = set()
	i = 0
	s = 0
	while s <= d:
		squares.add(s)
		i += 1
		s = i * i
	cnt = 0
	for a in squares:
		if a != 0 and d - a in squares:
			cnt += 1
	cnt *= 4
	if cnt <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt, ceil

def isCircleProtected(d, K):
	count = 0
	for m in range(int(ceil(sqrt(d)))):
		if sqrt(d - m * m).is_integer():
			count += 4
	return count <= K
t = int(input())
for _ in range(t):
	(d, k) = [int(x) for x in input().split(' ')]
	if isCircleProtected(d, k):
		print('possible')
	else:
		print('impossible')


import math
t = int(input())
for _ in range(t):
	(d, k) = tuple(map(int, input().split()))
	border_suburbs = 0
	for x in range(d):
		y_squared = d - x * x
		if y_squared < 0:
			break
		y = round(math.sqrt(y_squared))
		if y < x:
			break
		if x * x + y * y == d:
			if x == 0 or y == 0 or x == y:
				border_suburbs += 4
			else:
				border_suburbs += 8
	if border_suburbs <= k:
		print('possible')
	else:
		print('impossible')


from math import sqrt, ceil

def do(rsq, k):
	x = 1
	y = ceil(sqrt(rsq))
	needed = 0
	while x < y:
		sq = x ** 2 + y ** 2
		if sq > rsq:
			y -= 1
		else:
			if sq == rsq:
				needed += 1
			x += 1
	needed *= 8
	if x == y and x ** 2 + y ** 2 == rsq:
		needed += 4
	needed += 4 * (ceil(sqrt(rsq)) ** 2 == rsq)
	return needed <= k
q = int(input())
for _ in range(q):
	(rsq, k) = map(int, input().split())
	ok = do(rsq, k)
	print('possible' if ok else 'impossible')


from math import sqrt, ceil
t = int(input().strip())
for __ in range(t):
	(d, k) = input().strip().split(' ')
	(d, k) = (int(d), int(k))
	r = ceil(sqrt(d))
	suburb_count = 0
	for a in range(r):
		b = sqrt(d - a ** 2)
		if b == int(b):
			suburb_count += 4
			if k < suburb_count:
				print('impossible')
				break
	if k >= suburb_count:
		print('possible')


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


import math

def solve(d, k):
	points = set()
	for a in range(0, math.floor(math.sqrt(d)) + 1):
		b = math.sqrt(d - a ** 2)
		if round(b) != b:
			continue
		b = round(b)
		points.add((a, b))
		points.add((-a, b))
		points.add((a, -b))
		points.add((-a, -b))
		if len(points) > k:
			return False
	return True

def main():
	t = int(input().strip())
	for _ in range(t):
		(d, k) = map(int, input().strip().split(' '))
		if solve(d, k):
			print('possible')
		else:
			print('impossible')
main()


val = 0
squareset = set()
while True:
	sqr = val * val
	if sqr >= 2 * 10 ** 9:
		break
	val += 1
	squareset.add(sqr)
t = int(input())
for i in range(t):
	(d, k) = map(int, input().split())
	cnt = 0
	val = 0
	while True:
		sqr = val * val
		if sqr < d:
			othersq = d - sqr
			if othersq in squareset:
				cnt += 1
		if sqr >= d:
			break
		val += 1
	if k < 4 * cnt:
		print('impossible')
	else:
		print('possible')


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def r2(d):
	(d1, d3) = (0, 0)
	for i in factors(d):
		if i % 4 == 1:
			d1 += 1
		elif i % 4 == 3:
			d3 += 1
	return 4 * (d1 - d3)
t = int(input())
for _ in range(t):
	(d, k) = input().split()
	(d, k) = [int(d), int(k)]
	if r2(d) > k:
		print('impossible')
	else:
		print('possible')


import math
t = int(input())
for _ in range(t):
	(d, k) = [int(x) for x in input().split()]
	s = math.ceil(d ** 0.5)
	c = 0
	for i in range(0, s):
		j = (d - i * i) ** 0.5
		if j == int(j):
			c += 4
	if k >= c:
		print('possible')
	else:
		print('impossible')


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


from math import ceil

def lattice(n):
	res = 0
	r = ceil(n ** 0.5)
	for x in range(r):
		if ((n - x * x) ** 0.5).is_integer():
			res += 1
	return 4 * res
t = int(input().strip())
for _ in range(t):
	(d, k) = map(int, input().strip().split())
	s = lattice(d)
	if k < s:
		print('impossible')
	else:
		print('possible')


from math import sqrt

def do_work():
	(d, s) = [int(i) for i in input().split()]
	r = sqrt(d)
	lattice_points = 0
	x = 0
	while x < r:
		y = sqrt(d - x ** 2)
		if y == int(y):
			lattice_points += 4
		x += 1
	print('impossible' if lattice_points > s else 'possible')
T = int(input())
for _ in range(T):
	do_work()


import math
t = int(input())
for _ in range(t):
	(d, k) = [int(x) for x in input().split()]
	s = math.ceil(d ** 0.5)
	c = 0
	for i in range(0, s):
		j = (d - i * i) ** 0.5
		if j == int(j):
			c += 4
	if k >= c:
		print('possible')
	else:
		print('impossible')


import math
t = int(input())
for _ in range(t):
	(d, k) = [int(x) for x in input().split()]
	s = math.ceil(d ** 0.5)
	c = 0
	for i in range(0, s):
		j = (d - i * i) ** 0.5
		if j == int(j):
			c += 4
	if k >= c:
		print('possible')
	else:
		print('impossible')


import sys
import math
n = int(input().strip())
for k in range(n):
	(d, k) = input().strip().split(' ')
	(d, k) = [int(d), int(k)]
	i = 0
	i_sq = i * i
	while i_sq <= d >> 1:
		j = round(math.sqrt(d - i_sq))
		if j * j + i_sq == d:
			if i == 0 or j == 0 or i == j:
				k -= 4
			else:
				k -= 8
		i_sq += (i << 1) + 1
		i += 1
	if k >= 0:
		print('possible')
	else:
		print('impossible')


import math
t = int(input())
while t > 0:
	(d, k) = [int(x) for x in input().split()]
	s = math.ceil(d ** 0.5)
	c = 0
	for i in range(0, s):
		j = (d - i * i) ** 0.5
		if j == int(j):
			c += 4
	if k >= c:
		print('possible')
	else:
		print('impossible')
	t -= 1


from math import sqrt, ceil
(square_list, square_set) = (list(map(lambda x: x ** 2, range(44722))), set(map(lambda x: x ** 2, range(44722))))
print('\n'.join(map(lambda d, k: '{}possible'.format('im' if k < 4 * sum(map(lambda x: d - x in square_set, square_list[:int(ceil(sqrt(d)))])) else ''), *zip(*(map(int, input().strip().split()) for _ in range(int(input())))))))


import math
t = int(input())
for _ in range(t):
	(d, k) = [int(x) for x in input().split()]
	s = math.ceil(d ** 0.5)
	c = 0
	for i in range(0, s):
		j = (d - i * i) ** 0.5
		if j == int(j):
			c += 4
	if k >= c:
		print('possible')
	else:
		print('impossible')


from math import *
for _ in range(int(input())):
	(d, k) = map(int, input().split(' '))
	r = 0
	for x in range(0, ceil(sqrt(d))):
		y = d - x * x
		ys = int(sqrt(y))
		if ys * ys == y:
			r += 4
	if r > k:
		print('impossible')
	else:
		print('possible')


import math
T = int(input())
for i in range(T):
	[d, k] = [int(x) for x in input().split(' ')]
	lim = int(math.sqrt(d / 2)) + 1
	num = 0
	dup = False
	for x in range(lim):
		x2 = x * x
		y = int(math.sqrt(d - x2))
		if y * y + x2 == d:
			num += 1
			if x == 0:
				dup = True
	req = num * 8
	if dup:
		req -= 4
	if req > k:
		print('impossible')
	else:
		print('possible')


t = int(input().strip())
for a0 in range(t):
	x = input().strip().split()
	d = int(x[0])
	k = int(x[1])
	count = 0
	for i in range(int(d ** 0.5) + 1):
		if (d - i * i) ** 0.5 % 1 == 0:
			if i == 0 or d - i * i == 0:
				count += 2
			else:
				count += 4
	if k >= count:
		print('possible')
	else:
		print('impossible')


from math import sqrt

def solutionsOfEqn(d):
	count = 0
	for x in range(1, int(sqrt(d)) + 1):
		test = sqrt(d - x * x)
		if test.is_integer():
			count += 1
	return count

def isPossible(d, k):
	solns = solutionsOfEqn(d)
	if 4 * solns <= k:
		return 'possible'
	return 'impossible'
t = int(input())
for _ in range(t):
	inp = input().split()
	(d, k) = [int(inp[0]), int(inp[1])]
	res = isPossible(d, k)
	print(res)


import math
t = int(input())
for _ in range(t):
	(d, k) = [int(x) for x in input().split()]
	s = math.ceil(d ** 0.5)
	c = 0
	for i in range(0, s):
		j = (d - i * i) ** 0.5
		if j == int(j):
			c += 4
	if k >= c:
		print('possible')
	else:
		print('impossible')


def is_square(x):
	y = int(x ** 0.5)
	return y * y == x

def f(r, k):
	x_max = int(r ** 0.5)
	c = 0
	if x_max * x_max == r:
		c += 4
		x_max -= 1
	y = x_max
	for x in range(1, x_max + 1):
		if c >= k:
			break
		while y * y + x * x > r:
			y -= 1
		if y * y + x * x == r:
			c += 4
	return c >= k
nt = int(input().strip())
for t in range(nt):
	(r, k) = [int(e) for e in input().strip().split()]
	if f(r, k + 1):
		print('impossible')
	else:
		print('possible')


from bisect import bisect_left
import logging
squares = [x * x for x in range(44722)]

def count_pythag_trip(x):
	count_same = 0
	count_different = 0
	for y in squares:
		if 2 * y > x:
			break
		i = bisect_left(squares, x - y)
		if i != len(squares) and squares[i] + y == x:
			logging.debug('%s + %s = %s', squares[i], y, x)
			if squares[i] == y or squares[i] == x:
				count_same += 1
			else:
				count_different += 1
	return (count_same, count_different)
t = int(input())
for _ in range(t):
	[d, k] = [int(x) for x in input().split()]
	(y, z) = count_pythag_trip(d)
	n_cities = 4 * y + 8 * z
	logging.debug('integral points on circle: %s', n_cities)
	if n_cities > k:
		print('impossible')
	else:
		print('possible')


import sys
import math

def read_one():
	return int(input().strip())

def read_two():
	(x, y) = input().strip().split(' ')
	return [int(x), int(y)]

def execute(d, k):
	import math
	s = int(math.floor(math.sqrt(d)))
	count = 0
	for x in range(1, s + 1):
		y = int(math.floor(math.sqrt(d - x * x)))
		if x * x + y * y == d:
			count += 1
	if 4 * count <= k:
		print('possible')
	else:
		print('impossible')
t = read_one()
for _ in range(t):
	(d, k) = read_two()
	execute(d, k)


import math
q = int(input())
for a in range(q):
	(d, k) = map(int, input().split())
	r = int(math.sqrt(d))
	cnt = 0
	for i in range(r + 1):
		y = math.sqrt(d - i * i)
		if y.is_integer():
			cnt += 2 if y == 0 or i == 0 else 4
	print('impossible' if cnt > k else 'possible')


import math

def is_possible(d, max_stations):
	r = math.sqrt(d)
	count = 0
	for x in range(0, int(r) + 1):
		if x >= r:
			break
		y = math.sqrt(d - x * x)
		if float(int(y)) == y:
			count += 1
	if count * 4 > max_stations:
		print('impossible')
	else:
		print('possible')
num_tests = int(input().strip())
for i in range(0, num_tests):
	test_data = map(int, input().strip().split(' '))
	is_possible(*test_data)