primpatt_16191
There is a very large field, colored white and divided into squares. There is a coordinate system attached to the field: y-axis goes from south to north and x-axis goes from west to east. Sides of the squares are parallel to the axes. There is a robot in the (0, 0) square. Robot starts to move in spiral as depicted. First it moves one step east and one step north. Then two steps west and two steps south. Then three steps east and three steps north, four steps west and four steps south and so on. It moves to a new square with each step. As it moves it counts squares it passes and, if the number of the square is the prime number, then the robot fills this square with black color. The (0, 0) square has the number 0. Given the coordinates of a square you are to calculate the distance from this square to the nearest to it black square. For two squares with coordinates (x1, y1) and (x2, y2) the distance between those squares is |x1-x2|+|y1-y2|.


Input
Input file consists of a set of tests. The first line of the file is number T – the number of tests (T <= 500). Following T lines contains two integers each separated with a space: x and y – the coordinates of the square (-2000001 < x < 2000001, -2000001 < y < 2000001).


Output
For each coordinate pair in the input file you are to output the distance between this square and the nearest to it black square.


Example

Input:
8
0 0
1 0
1 1
0 1
3 3
-3 -3
-1 2
0 -3

Output:
1
1
0
0
1
1
2
2
def millerRabin(n):
	# Returns true if probable prime, false if composite
	bases     = [2,3,5,7,11,13,17,19,23]
	nm1       = n-1
	m         = nm1
	d         = 0

	if n in bases:
		return True
	if n < 2:
		return False

	while not m&1:
		d    += 1
		m   >>= 1

	for a in bases:
		done_for_base = False

		b   = pow(a,m,n)
		if b == 1 or b == nm1 :
			#done_for_base = True
			continue
		for k in range(d-1):
			b = pow(b,2,n)
			if b == 1:
				return False
			elif b == nm1:
				done_for_base = True
				break
		if not done_for_base:
			return False
	return True

def valAt(x,y):
	if x>y:
		if x+y > 0:
			n  = 4*x*x - 3*x + y
		else :
			n  = 4*y*y - 3*y + x
	else:
		if x+y > 0:
			n  = 4*y*y -  x - y
		else :
			n  = 4*x*x -  y - x
	return n

def solveCase(x,y):
	r    = 0
	n    = valAt(x,y)
	if millerRabin(n):
		return r
	while True:
		r  += 1
		for k in range(r):
			n1  = valAt(x + r-k, y + 0-k)
			n2  = valAt(x + 0-k, y - r+k)
			n3  = valAt(x - r+k, y + 0+k)
			n4  = valAt(x + 0+k, y + r-k)
			for n in [n1,n2,n3,n4]:
				if millerRabin(n):
					return r

def main():
	T  = int(raw_input(''))
	for t in range(T):
		x,y = [ int(i) for i in raw_input().split() ]
		ans = solveCase(x,y)
		print ans


main()