Eric has four integers $a$, ${b}$, ${c}$, and ${d}$. 

Instantly, he wondered how many pairs of integers, $(x,y)$, satisfy the following equation:

$x^2+y^2=(x\times a)+(y\times b)$

where $1\leq x\leq c$ and $1\leq y\leq d$. 

Find and print the number of pairs that satisfy the above equation.  

Input Format

The first line contains an integer ${q}$, the number of queries. 

${q}$ lines follow, each containing four integers, ${a}$, ${b}$, ${c}$, and ${d}$, in that order.  

Constraints

$1\leq q\leq10$  
$1\leq a,b,c,d\leq10^5$

Output Format

For each test case, print one line, the number of pairs $(x,y)$ that are valid solutions to Eric's equation.   

Sample Input 0
1
1 1 1 1

Sample Output 0
1

Explanation 0

The solution to $x^2+y^2=x+y$, where $1\leq x\leq1$ and $1\leq y\leq1$ is $x=1$, $y=1$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Matrices


Solutions:
def solve(a, b, c, d):
	res = 0
	for x in range(1, c + 1):
		l = x * (x - a)
		det2 = b * b - 4 * l
		if det2 == 0 and b % 2 == 0 and (1 <= b // 2 <= d):
			res += 1
			continue
		if det2 > 0:
			det = int(round(det2 ** 0.5))
			if det * det == det2 and (b + det) % 2 == 0:
				if 1 <= (b + det) // 2 <= d:
					res += 1
				if 1 <= (b - det) // 2 <= d:
					res += 1
	return res
for _ in range(int(input())):
	print(solve(*map(int, input().split())))


import sys

def is_square(n):
	if n < 0:
		return -1
	if int(n ** 0.5 + 0.5) ** 2 == n:
		return int(n ** 0.5 + 0.5)
	return -1

def countSolutions(a, b, c, d):
	ans = 0
	for y in range(1, d + 1):
		alpha = 1
		beta = -a
		gamma = y * y - y * b
		D = beta ** 2 - 4 * gamma * alpha
		if D < 0:
			continue
		if is_square(D) == -1:
			continue
		x = is_square(D)
		if (-beta + x) % 2 == 0:
			x1 = (-beta + x) // 2
			x2 = (-beta - x) // 2
			if 1 <= x1 and x1 <= c:
				ans += 1
			if 1 <= x2 and x2 <= c and (x1 != x2):
				ans += 1
	return ans
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def nsqr(x):
	if x < 0:
		return 0
	a = int(math.sqrt(x))
	if a * a == x:
		return a
	if (a + 1) * (a + 1) == x:
		return a + 1
	return 0

def countSolutions(a, b, c, d):
	r = a * a + b * b
	solset = set()
	for p in range(-a - b, a + b + 1):
		if p * p > r:
			continue
		q = nsqr(r - p * p)
		if p * p + q * q != r:
			continue
		if (p + a) % 2 == 0 and (q + b) % 2 == 0:
			(x, y) = ((p + a) // 2, (q + b) // 2)
			if c >= x >= 1 and d >= y >= 1 and (x * x + y * y == a * x + b * y):
				solset.add((x, y))
		q = -q
		if (p + a) % 2 == 0 and (q + b) % 2 == 0:
			(x, y) = ((p + a) // 2, (q + b) // 2)
			if c >= x >= 1 and d >= y >= 1 and (x * x + y * y == a * x + b * y):
				solset.add((x, y))
	return len(solset)
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		det = b ** 2 - 4 * (x ** 2 - a * x)
		if det < 0:
			continue
		det = det ** (1 / 2)
		if int(det) == det:
			if det == 0:
				if b % 2 == 0:
					if b // 2 > 0 and b // 2 <= d:
						count += 1
			elif (int(det) + b) % 2 == 0:
				if (int(det) + b) // 2 > 0 and (int(det) + b) // 2 <= d:
					count += 1
				if (-int(det) + b) // 2 > 0 and (-int(det) + b) // 2 <= d:
					count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from math import sqrt, trunc

def countSolutions(a, b, c, d):
	count = 0
	for y in range(1, d + 1):
		disc = a * a - 4 * y * y + 4 * y * b
		if disc >= 0 and sqrt(disc).is_integer():
			x1 = round((a + sqrt(disc)) / 2)
			x2 = round((a - sqrt(disc)) / 2)
			if 1 <= x1 <= c:
				count += 1
			if 1 <= x2 <= c and x1 != x2:
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math
import sys

def is_valid_y(y, a, b, d, x):
	if not 1 <= y <= d:
		return False
	return y * y - y * b + x * x - x * a == 0

def countSolutions(a, b, c, d):
	res = 0
	for x in range(1, c + 1):
		sqinner = b * b + 4 * x * a - 4 * x * x
		if sqinner < 0:
			continue
		sqpart = int(math.sqrt(sqinner))
		(y1, y2) = ((b + sqpart) // 2, (b - sqpart) // 2)
		if is_valid_y(y1, a, b, d, x):
			res += 1
		if y2 != y1 and is_valid_y(y2, a, b, d, x):
			res += 1
	return res
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from collections import defaultdict

def count(a, b, c, d):
	X = defaultdict(int)
	for x in range(1, c + 1):
		X[x * x - a * x] += 1
	Y = defaultdict(int)
	for y in range(1, d + 1):
		Y[b * y - y * y] += 1
	cpt = 0
	for x in X:
		cpt += X[x] * Y[x]
	return cpt

def main():
	q = int(input())
	for _ in range(q):
		(a, b, c, d) = map(int, input().split())
		print(count(a, b, c, d))
main()


import sys

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		D = b ** 2 - 4 * (x ** 2 - a * x)
		if D < 0:
			continue
		D = D ** 0.5
		if int(D) == D:
			if D == 0:
				if b % 2 == 0:
					y = b // 2
					if 1 <= y <= d:
						count += 1
			else:
				if (b + D) % 2 == 0:
					y = (b + D) // 2
					if 1 <= y <= d:
						count += 1
				if (b - D) % 2 == 0:
					y = (b - D) // 2
					if 1 <= y <= d:
						count += 1
	return count
q = int(input().strip())
for _ in range(q):
	(a, b, c, d) = [int(x) for x in input().split()]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def countSolutions(a, b, c, d):
	sols = set()
	for x in range(1, c + 1):
		D = b ** 2 - 4 * (x ** 2 - a * x)
		if D < 0:
			continue
		disc = sqrt(D)
		if disc == round(disc):
			disc = int(disc)
		else:
			continue
		if (b - disc) % 2 != 0:
			continue
		ys = ((b + disc) // 2, (b - disc) // 2)
		for y in ys:
			if 1 <= y <= d:
				sols.add((x, y))
	return len(sols)
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from collections import Counter

def solve(a, c):
	count = Counter()
	for x in range(1, c + 1):
		count[x * x - x * a] += 1
	return count

def countSolutions(a, b, c, d):
	x = solve(a, c)
	y = solve(b, d)
	ans = 0
	for k in x:
		ans += x[k] * y[-k]
	return ans
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math
q = int(input())
while q:
	q -= 1
	(a, b, c, d) = list(map(int, input().split()))
	ans = 0
	for i in range(1, c + 1):
		bb = -b
		cc = i * i - i * a
		if bb ** 2 - 4 * cc > 0:
			kk = math.sqrt(bb ** 2 - 4 * cc)
			if (bb + kk) % 2 == 0 and (-bb - kk) / 2 >= 1 and ((-bb - kk) / 2 <= d):
				ans += 1
			if (-bb + kk) % 2 == 0 and (-bb + kk) / 2 >= 1 and ((-bb + kk) / 2 <= d):
				ans += 1
		if bb ** 2 - 4 * cc == 0:
			if bb % 2 == 0 and -bb / 2 >= 1 and (-bb / 2 <= d):
				ans += 1
	print(ans)


import sys
import math

def countSolutions(a, b, c, d):
	total = 0
	for i in range(1, c + 1):
		m = i ** 2 - a * i
		if b ** 2 - 4 * m >= 0:
			y = (b + math.sqrt(b ** 2 - 4 * m)) / 2
			if y >= 1 and y <= d and (y == int(y)):
				total += 1
			z = (b - math.sqrt(b ** 2 - 4 * m)) / 2
			if z >= 1 and z <= d and (z == int(z)):
				total += 1
			if z == y:
				total -= 1
	return total
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math

def count(a, b, c, d):
	solutions = set()
	for x in range(1, c + 1):
		disc = b ** 2 - 4 * (x * (x - a))
		if disc < 0:
			continue
		disc = math.sqrt(disc)
		y = (b + disc) / 2
		if y.is_integer() and 1 <= y <= d:
			solutions.add((x, int(y)))
		y = (b - disc) / 2
		if y.is_integer() and 1 <= y <= d:
			solutions.add((x, int(y)))
	return len(solutions)
for _ in range(int(input().strip())):
	(a, b, c, d) = [int(x) for x in input().strip().split(' ')]
	print(count(a, b, c, d))


import sys
from math import sqrt, floor, ceil

def countSolutions(a, b, c, d):
	count = 0
	low_x = ceil((a - sqrt(a ** 2 + b ** 2)) / 2)
	high_x = floor((a + sqrt(a ** 2 + b ** 2)) / 2)
	for x in range(max(1, low_x), min(c, high_x) + 1):
		det = b ** 2 - 4 * x ** 2 + 4 * a * x
		if det < 0:
			continue
		sq = sqrt(det)
		if det != 0 and sq != int(det / sq):
			continue
		if (b - sq) % 2 == 1:
			continue
		y1 = (b - sq) // 2
		y2 = (b + sq) // 2
		if 1 <= y1 <= d:
			count += 1
		if 1 <= y2 <= d and sq != 0:
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


for _ in range(int(input())):
	(a, b, c, d) = [int(x) for x in input().split()]
	n = a * a + b * b
	sols = set()
	for i in range(int(n ** 0.5) + 1):
		f = n - i * i
		g = int(f ** 0.5)
		if g * g == f:
			sols |= {(i, g), (i, -g), (-i, g), (-i, -g)}
	res = 0
	for (p, q) in sols:
		if (p + a) % 2 == 0 and (q + b) % 2 == 0:
			if 1 <= (p + a) // 2 <= c and 1 <= (q + b) // 2 <= d:
				res += 1
	print(res)


sqrt = {}
s = 0
s2 = 0
q = int(input())
for qq in range(q):
	(a, b, c, d) = map(int, input().split())
	count = 0
	for x in range(1, c + 1):
		D = b * b - 4 * x * (x - a)
		while D >= s2:
			sqrt[s2] = s
			s += 1
			s2 = s * s
		if D not in sqrt:
			continue
		D = sqrt[D]
		y = b + D
		if y & 1:
			continue
		y //= 2
		if y >= 1 and y <= d:
			count += 1
		y = (b - D) // 2
		if D > 0 and y >= 1 and (y <= d):
			count += 1
	print(count)


import sys
from collections import Counter

def countSolutions(a, b, c, d):
	xl = [x * x - a * x for x in range(1, c + 1)]
	yl = [b * y - y * y for y in range(1, d + 1)]
	xc = Counter(xl)
	yc = Counter(yl)
	ctr = 0
	for (k, v) in xc.items():
		if k in yc:
			ctr += v * yc[k]
	return ctr
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def is_square(D):
	if D < 0:
		return False
	a = D
	while a * a > D:
		a = int((a + int(D / a)) / 2)
	return a * a == D

def newton_sqrt(D):
	x = D / 2
	memory = 0
	while x != memory:
		memory = x
		x = int((x ** 2 + D) / (2 * x))
	return x

def countSolutions(a, b, c, d):
	counter = 0
	for x in range(1, c + 1):
		D = b * b - 4 * (x * x - a * x)
		if is_square(D):
			omg = newton_sqrt(D)
			y = (b + omg) / 2
			if y == int(y) and y > 0 and (y < d + 1):
				counter += 1
			if omg != 0:
				y = (b - omg) / 2
				if y == int(y) and y > 0 and (y < d + 1):
					counter += 1
	return counter
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from math import ceil
from math import sqrt
for _ in range(int(input())):
	[a, b, c, d] = [int(i) for i in input().split()]
	rad = sqrt(a ** 2 + b ** 2) / 2
	r = min(int(rad + rad), c)
	o = 0
	for i in range(1, r + 1):
		p = -1
		try:
			r1 = (b - sqrt(b * b - 4 * (i * i - a * i))) / 2
			if r1 >= 1.0 and r1 <= float(d) and (float(int(r1)) == r1):
				p = r1
				o += 1
		except:
			pass
		try:
			r2 = (b + sqrt(b * b - 4 * (i * i - a * i))) / 2
			if r2 >= 1.0 and r2 <= float(d) and (float(int(r2)) == r2) and (r2 != p):
				o += 1
		except:
			pass
	print(o)


import sys
import math as m

def countSolutions(a, b, c, d):
	counter = 0
	for x in range(1, c + 1):
		if b * b - 4 * (x * x - x * a) == 0:
			if (b <= 2 * d) & (b >= 2):
				counter += 1
		if b * b - 4 * (x * x - x * a) > 0:
			s = int(m.sqrt(b * b - 4 * (x * x - x * a)))
			if s * s == b * b - 4 * (x * x - x * a):
				if s % 2 == b % 2:
					if (b - s <= 2 * d) & (b - s >= 2):
						counter += 1
					if (b + s <= 2 * d) & (b + s >= 2):
						counter += 1
	return counter
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	k = math.sqrt(b * b + a * a)
	yl = int(math.floor((b + k) / 2))
	xl = int(math.floor((a + k) / 2))
	d = min(yl, d)
	c = min(xl, c)
	if c > d:
		k = a
		a = b
		b = k
		k = c
		c = d
		d = k
	p = 0
	for i in range(c):
		x = i + 1
		k2 = b * b - 4 * (x * x - x * a)
		k = int(math.sqrt(k2))
		if k * k == k2:
			y1 = b - k
			y2 = b + k
			t = 0
			if y1 % 2 == 0:
				if y1 > 0 and y1 <= d * 2:
					t = t + 1
			if y2 % 2 == 0:
				if y2 > 0 and y2 <= d * 2:
					t = t + 1
			if t == 2:
				if y1 == y2:
					p = p + 1
				else:
					p = p + 2
			else:
				p = p + t
	return p
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from math import sqrt
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	ans = 0
	for x in range(1, c + 1):
		sy = (a ** 2 + b ** 2) / 4 - (x - a / 2) ** 2
		if sy >= 0:
			y1 = int(round(sqrt(sy) + b / 2))
			y2 = int(round(-sqrt(sy) + b / 2))
			if (y1 - b / 2) ** 2 == sy and 1 <= y1 <= d:
				ans += 1
			if (y2 - b / 2) ** 2 == sy and 1 <= y2 <= d:
				ans += 1
			if y1 == y2:
				ans -= 1
	print(ans)


import sys

def countSolutions(a, b, c, d):
	B = -b
	A = 1
	soln_set = set()
	for x in range(1, c + 1):
		C = x * (x - a)
		if B ** 2 - 4 * A * C < 0:
			continue
		desc = (B ** 2 - 4 * A * C) ** 0.5
		y = []
		y1 = (-B + desc) / 2 / A
		if int(y1) == y1:
			y.append(int(y1))
		y2 = (-B - desc) / 2 / A
		if int(y2) == y2:
			y.append(int(y2))
		for yi in y:
			if yi > 0 and yi <= d:
				soln_set.add((x, yi))
	return len(soln_set)
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math
q = int(input())
for i in range(q):
	(a, b, c, d) = list(map(int, input().strip().split()))
	ans = 0
	for y in range(1, d + 1):
		n = a * a - 4 * y * y + 4 * y * b
		if n >= 0 and math.sqrt(n) % 1 == 0:
			if (a + int(math.sqrt(n))) // 2 >= 1 and (a + int(math.sqrt(n))) // 2 <= c:
				ans += 1
			if (a - int(math.sqrt(n))) // 2 >= 1 and (a - int(math.sqrt(n))) // 2 <= c:
				ans += 1
			if int(math.sqrt(n)) == 0 and a // 2 >= 1 and (a // 2 <= c):
				ans -= 1
	print(ans)


from math import sqrt

def countSolutions(a, b, c, d):
	s = 0
	for x in range(1, c + 1):
		square = b * b - 4 * (x * x - x * a)
		if square < 0:
			continue
		root = int(sqrt(square))
		if root * root == square:
			sol1 = (b + root) // 2
			sol2 = (b - root) // 2
			for sol in set([sol1, sol2]):
				if 1 <= sol and sol <= d:
					s += 1
	return s
q = int(input().strip())
for _ in range(q):
	(a, b, c, d) = map(int, input().strip().split())
	result = countSolutions(a, b, c, d)
	print(result)


from math import sqrt

def countSolutions(a, b, c, d):
	ans = set()
	b2 = b ** 2
	for x in range(1, c + 1):
		u = x * (x - a)
		delta = b2 - 4 * u
		if delta < 0:
			continue
		sq_delta = int(sqrt(delta))
		if sq_delta ** 2 != delta:
			continue
		(y1, y2) = ((b + sq_delta) / 2, (b - sq_delta) / 2)
		if not y1.is_integer():
			continue
		(y1, y2) = (int(y1), int(y2))
		if 0 < y1 <= d:
			ans.add((x, y1))
		if 0 < y2 <= d:
			ans.add((x, y2))
	return len(ans)
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math as m

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		sq = b ** 2 - 4 * (x ** 2 - a * x)
		if sq == 0:
			y = b / 2
			if y - int(y) == 0 and 1 <= y <= d:
				count += 1
		elif sq > 0:
			sq = m.sqrt(sq)
			y1 = (b + sq) / 2
			y2 = (b - sq) / 2
			if y1 - int(y1) == 0 and 1 <= y1 <= d:
				count += 1
			if y2 - int(y2) == 0 and 1 <= y2 <= d:
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	ans = set()
	for x in range(1, c + 1):
		delta = b * b - 4 * (x * x - x * a)
		if delta < 0:
			continue
		delta = math.sqrt(delta)
		if int(delta) != delta:
			continue
		for y in [(b + delta) / 2, (b - delta) / 2]:
			if int(y) != y or y > d or y < 1:
				continue
			if x * x + y * y == x * a + y * b:
				ans.add((x, y))
	return len(ans)
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def cond(x, y, a, b):
	return x * x + y * y == x * a + y * b

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		e = x * x - x * a
		if b * b - 4 * e < 0:
			continue
		D = int(math.sqrt(b * b - 4 * e))
		if D * D != b * b - 4 * e:
			continue
		y1 = (b + D) // 2
		y2 = (b - D) // 2
		if 1 <= y1 <= d and cond(x, y1, a, b):
			count += 1
		if 1 <= y2 <= d and cond(x, y2, a, b) and (y2 != y1):
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def countSolutions(a, b, c, d):
	C = a * a + b * b
	cnt = 0
	for x in range(1, c + 1):
		D = C - (2 * x - a) ** 2
		if D < 0:
			break
		_D = round(sqrt(D))
		if D != _D * _D:
			continue
		if (b + _D) % 2:
			continue
		if 1 <= (b + _D) // 2 <= d:
			cnt += 1
		if 1 <= (b - _D) // 2 <= d and _D != 0:
			cnt += 1
	return cnt
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def isqrt(n):
	x = n
	y = (x + 1) // 2
	while y < x:
		x = y
		y = (x + n // x) // 2
	return x

def countSolutions(a, b, c, d):
	counter = 0
	for y in range(1, d + 1):
		D_sqr = a * a + 4 * y * (b - y)
		D = isqrt(D_sqr)
		if D * D != D_sqr:
			continue
		if a % 2 != D % 2:
			continue
		if D != 0:
			sols = [(a + D) // 2, (a - D) // 2]
		else:
			sols = [a // 2]
		for sol in sols:
			if sol < 1 or sol > c:
				continue
			counter += 1
	return counter
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		idet = b * b - 4 * (x * x - a * x)
		if idet < 0:
			continue
		det = sqrt(idet)
		temp1 = (b + det) / 2
		temp2 = (b - det) / 2
		if temp1 % 1 == 0 and temp1 >= 1 and (temp1 <= d):
			count += 1
		if temp2 % 1 == 0 and temp2 >= 1 and (temp2 <= d):
			count += 1
		if temp1 == temp2:
			count -= 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def is_square(integer):
	root = math.sqrt(integer)
	if int(root + 0.5) ** 2 == integer:
		return True
	else:
		return False

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		disc = b ** 2 - 4 * (x ** 2 - a * x)
		if disc < 0:
			continue
		if not is_square(disc):
			continue
		root_disc = int(math.sqrt(disc))
		if b % 2 != root_disc % 2:
			continue
		y_1 = (b + root_disc) // 2
		y_2 = (b - root_disc) // 2
		if 1 <= y_1 <= d:
			count += 1
		if disc != 0 and 1 <= y_2 <= d:
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def isSquare(x):
	root = x ** 0.5
	if root.is_integer():
		return int(root)
	return -1

def countSolutions(a, b, c, d):
	count = 0
	r = (a ** 2 + b ** 2) ** 0.5 / 2
	minX = max(1, round(a / 2 - r + 0.5))
	maxX = min(c, int(a / 2 + r))
	for x in range(minX, maxX + 1):
		squared = isSquare(a ** 2 + b ** 2 - (2 * x - a) ** 2)
		if squared < 0:
			continue
		if (squared + b) % 2 == 0:
			y = (squared + b) // 2
			count += y >= 1 and y <= d
			if squared != 0:
				y = (b - squared) // 2
				count += y >= 1 and y <= d
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	sol = 0
	for y in range(1, d + 1):
		det = a ** 2 - 4 * y ** 2 + 4 * y * b
		if det < 0:
			continue
		det = det ** 0.5
		(x1, x2) = ((a + det) / 2, (a - det) / 2)
		if x1 >= 1 and x1 <= c and (x1 % 1 == 0):
			sol += 1
		if x2 >= 1 and x2 <= c and (x2 % 1 == 0):
			sol += 1
			if det == 0:
				sol -= 1
	return sol
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	i = 1
	k = b / 2
	if k % 1 == 0 and k > 0 and (k < d + 1):
		k = 1
	while i <= c:
		e = b * b - 4 * (i * i - i * a)
		if e < 0:
			break
		if e == 0 and k == 1:
			count = count + 1
		else:
			res = (b + math.sqrt(e)) / 2
			if res % 1 == 0 and res > 0 and (res < d + 1):
				count = count + 1
			res1 = (b - math.sqrt(e)) / 2
			if res1 % 1 == 0 and res1 > 0 and (res1 < d + 1):
				count = count + 1
		i = i + 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		C = x * x - a * x
		if b * b < 4 * C:
			continue
		D = int(math.sqrt(b * b - 4 * C))
		if D * D != b * b - 4 * C:
			continue
		y1 = (b + D) / 2
		y2 = (b - D) / 2
		y1 = int(y1) if y1 == int(y1) else -1
		y2 = int(y2) if y2 == int(y2) else -1
		if y1 >= 1 and y1 <= d:
			count += 1
		if y2 >= 1 and y2 <= d and (y2 != y1):
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	temp1 = [x * (x - a) for x in range(1, c + 1)]
	temp2 = [y * (b - y) for y in range(1, d + 1)]
	from collections import Counter
	c1 = Counter(temp1)
	c2 = Counter(temp2)
	res = 0
	for x in c1:
		res += c1[x] * c2[x]
	return res
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		m = x * (x - a)
		if m == 0:
			if 1 <= b <= d:
				count += 1
		else:
			temp = b * b - 4 * m
			if temp >= 0:
				if temp == 0:
					if 1 <= b / 2 <= d:
						count += 1
				elif math.sqrt(temp).is_integer():
					root1 = (b - math.sqrt(temp)) / 2
					root2 = (b + math.sqrt(temp)) / 2
					if 1 <= root1 <= d:
						count += 1
					if 1 <= root2 <= d:
						count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def countSolutions(a, b, c, d):
	count = 0
	bound = int(min([c, sqrt((a / 2) ** 2 + (b / 2) ** 2) + a / 2]))
	t = b / 2 - sqrt((a / 2) ** 2 + (b / 2) ** 2)
	if a / 2 - int(a / 2) == 0:
		if t > 0 and t - int(t) == 0:
			count += 1
	for x in range(1, bound + 1):
		y = sqrt((b / 2) ** 2 - x ** 2 + a * x) + b / 2
		z = b / 2 - sqrt((b / 2) ** 2 - x ** 2 + a * x)
		if y != z:
			if y - int(y) == 0 and y >= 1 and (y <= d):
				count += 1
			if z - int(z) == 0 and z >= 1 and (z <= d):
				count += 1
		elif y - int(y) == 0 and y >= 1 and (y <= d):
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	count = 0
	if c < ((a / 2) ** 2 + (b / 2) ** 2) ** (1 / 2) + a / 2:
		bound = c
	else:
		bound = int(((a / 2) ** 2 + (b / 2) ** 2) ** (1 / 2) + a / 2)
	if a / 2 - a // 2 == 0:
		t = b / 2 - ((a / 2) ** 2 + (b / 2) ** 2) ** (1 / 2)
		if t - int(t) == 0 and t >= 1:
			count = 1
	for i in range(1, bound + 1):
		y = ((b / 2) ** 2 - i ** 2 + a * i) ** (1 / 2) + b / 2
		z = -((b / 2) ** 2 - i ** 2 + a * i) ** (1 / 2) + b / 2
		if y != z:
			if y - int(y) == 0 and y <= d and (1 <= y):
				count += 1
			if z - int(z) == 0 and 1 <= z and (z <= d):
				count += 1
		elif y - int(y) == 0 and y <= d and (1 <= y):
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for i in range(1, c + 1):
		e0 = b * b - 4 * i * (i - a)
		if e0 < 0:
			continue
		e1 = math.sqrt(e0)
		e2 = (b + e1) / 2
		e3 = (b - e1) / 2
		if e2 >= 1 and e2 <= d and (math.ceil(e2) == math.floor(e2)):
			count = count + 1
			if e2 == e3:
				count = count - 1
		if e3 >= 1 and e3 <= d and (math.ceil(e3) == math.floor(e3)):
			count = count + 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from math import sqrt
import sys

def is_square(apositiveint):
	if apositiveint == 1:
		return True
	x = apositiveint // 2
	seen = set([x])
	while x * x != apositiveint:
		x = (x + apositiveint // x) // 2
		if x in seen:
			return False
		seen.add(x)
	return True

def countSolutions(a, b, c, d):
	ans = 0
	for x in range(1, c + 1):
		dscr = b * b - 4 * (x * x - a * x)
		if dscr == 0:
			ans += 1
		elif dscr > 0 and is_square(dscr):
			y1 = (b + sqrt(dscr)) / 2
			y2 = (b - sqrt(dscr)) / 2
			if d >= y1 >= 1:
				ans += 1
			if d >= y2 >= 1:
				ans += 1
	return ans
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math

def countSolutions(a, b, c, d):
	cnt = 0
	for x in range(1, c + 1):
		con = -x * (a - x)
		discr = b * b - 4 * con
		if discr >= 0:
			y = set([(b + math.sqrt(discr)) / 2, (b - math.sqrt(discr)) / 2])
			for yi in y:
				if yi == int(yi) and yi >= 1 and (yi <= d):
					cnt += 1
	return cnt
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	counter = 0
	for x in range(1, c + 1):
		if b ** 2 + 4 * a * x - 4 * x ** 2 >= 0:
			pRoot = (b - math.sqrt(b ** 2 + 4 * a * x - 4 * x ** 2)) / 2
			nRoot = (b + math.sqrt(b ** 2 + 4 * a * x - 4 * x ** 2)) / 2
			if pRoot.is_integer() and pRoot > 0 and (pRoot <= d):
				counter += 1
			if nRoot.is_integer() and nRoot > 0 and (nRoot <= d) and (nRoot != pRoot):
				counter += 1
	return counter
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def countSolutions(a, b, c, d):
	count = 0
	for y in range(1, d + 1):
		if a * a - 4 * (y * y - y * b) >= 0:
			x1 = (a + sqrt(a * a - 4 * (y * y - y * b))) / 2
			if x1 % 1 == 0 and 1 <= x1 <= c:
				count += 1
			x2 = (a - sqrt(a * a - 4 * (y * y - y * b))) / 2
			if x2 % 1 == 0 and 1 <= x2 <= c and (x1 != x2):
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math
import sys

def countSolutions(a, b, c, d):
	cnt = 0
	if c < d:
		return countSolutions(b, a, d, c)
	r_squared = (a * a + b * b) / 4
	for y in range(1, d + 1):
		y_2 = (y - b / 2) * (y - b / 2)
		if y_2 <= r_squared:
			x_pot = math.sqrt(r_squared - y_2) + a / 2
			x_pot_2 = -x_pot + a
			for x in set([x_pot, x_pot_2]):
				if x.is_integer() and x >= 1 and (x <= c):
					cnt += 1
	return cnt
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		(A, B, C) = (1, -b, x ** 2 - x * a)
		delta = B ** 2 - 4 * A * C
		if delta > 0:
			delta_sr = round(delta ** 0.5)
			if delta_sr ** 2 == delta:
				y = round((-B + delta_sr) / 2)
				if y >= 1 and y <= d:
					count += 1
				y = round((-B - delta_sr) / 2)
				if y >= 1 and y <= d:
					count += 1
		elif delta == 0:
			y = round(-B / 2)
			if y >= 1 and y <= d:
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for y in range(1, d + 1):
		val = a * a - 4 * (y * y - b * y)
		if val < 0:
			continue
		sqrt_val = math.sqrt(val)
		floor_sqrt_val = math.floor(sqrt_val)
		if floor_sqrt_val * floor_sqrt_val != val:
			continue
		numerator_1 = a + floor_sqrt_val
		numerator_2 = a - floor_sqrt_val
		if numerator_1 % 2 == 1:
			continue
		x_1 = numerator_1 / 2
		x_2 = numerator_2 / 2
		if x_1 > 0 and x_1 <= c:
			count += 1
		if x_2 > 0 and x_2 <= c and (x_2 != x_1):
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def squares(n):
	return set([x * x for x in range(n)])

def is_square(apositiveint):
	x = apositiveint // 2
	seen = set([x])
	while x * x != apositiveint:
		if x == 0:
			return True
		x = (x + apositiveint // x) // 2
		if x in seen:
			return False
		seen.add(x)
	return True

def poly(x, a, b, d):
	t = b * b - 4 * (x * x - a * x)
	solutions = 0
	if t < 0:
		pass
	elif t == 0:
		ans = b / 2
		if ans.is_integer() and 1 <= ans <= d:
			solutions += 1
	else:
		t1 = sqrt(t)
		ans = (b + t1) / 2
		if ans.is_integer() and 1 <= ans <= d:
			solutions += 1
		ans = (b - t1) / 2
		if ans.is_integer() and 1 <= ans <= d:
			solutions += 1
	return solutions

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		count += poly(x, a, b, d)
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	s = 0
	for y in range(1, d + 1):
		delta = a * a - 4 * (y * y - b * y)
		if delta == 0:
			x = a / 2
			res = x * x - a * x + y * y - b * y
			if int(x) == x and res == 0 and (x >= 1) and (x <= c):
				s = s + 1
		elif delta > 0:
			x1 = (a - math.sqrt(delta)) / 2
			x2 = (a + math.sqrt(delta)) / 2
			res1 = x1 * x1 - a * x1 + y * y - b * y
			res2 = x2 * x2 - a * x2 + y * y - b * y
			if int(x1) == x1 and res1 == 0 and (x1 >= 1) and (x1 <= c):
				s = s + 1
			if int(x2) == x2 and res2 == 0 and (x2 >= 1) and (x2 <= c):
				s = s + 1
	return s
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = int(0)
	if c >= d:
		for y in range(1, d + 1, 1):
			sol = y * (b - y)
			a1 = 1
			b1 = 0 - a
			c1 = 0 - sol
			disc = b1 * b1 - 4 * a1 * c1
			if disc >= 0:
				sol1 = (0 - b1 + math.sqrt(disc)) / (2 * a1)
				sol2 = (0 - b1 - math.sqrt(disc)) / (2 * a1)
				if sol1 == sol2:
					if math.ceil(sol1) == math.floor(sol1):
						if sol1 >= 1 and sol1 <= c:
							count += 1
				else:
					if sol1 >= 1 and sol1 <= c and (math.ceil(sol1) == math.floor(sol1)):
						count += 1
					if sol2 >= 1 and sol2 <= c and (math.ceil(sol2) == math.floor(sol2)):
						count += 1
	else:
		for x in range(1, c + 1, 1):
			sol = x * (x - a)
			a1 = 1
			b1 = 0 - b
			c1 = sol
			disc = b1 * b1 - 4 * a1 * c1
			if disc >= 0:
				sol1 = (0 - b1 + math.sqrt(disc)) / (2 * a1)
				sol2 = (0 - b1 - math.sqrt(disc)) / (2 * a1)
				if sol1 == sol2:
					if sol1 >= 1 and sol1 <= d and (math.ceil(sol1) == math.floor(sol1)):
						count += 1
				else:
					if sol1 >= 1 and sol1 <= d and (math.ceil(sol1) == math.floor(sol1)):
						count += 1
					if sol2 >= 1 and sol2 <= d and (math.ceil(sol2) == math.floor(sol2)):
						count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math

def countSolutions(a, b, c, d):
	count = 0
	if a <= c and b <= d:
		count += 1
	for x in range(1, min(c + 1, a)):
		D = b * b + 4 * x * (a - x)
		srd = int(round(math.sqrt(D)))
		if srd * srd == D and (b + srd) // 2 <= d:
			count += 1
	for y in range(1, min(d + 1, b)):
		D = a * a + 4 * y * (b - y)
		srd = int(round(math.sqrt(D)))
		if srd * srd == D and (a + srd) // 2 <= c:
			count += 1
	return count
q = int(input())
for _ in range(q):
	(a, b, c, d) = map(int, input().split())
	result = countSolutions(a, b, c, d)
	print(result)


import math
import sys

def countSolutions(a, b, c, d):
	t = 0
	for x in range(1, c + 1):
		try:
			r = math.sqrt(b * b + 4 * x * (a - x))
			y1 = (b + r) / 2
			y2 = (b - r) / 2
			if 1 <= y1 <= d and y1 == int(y1):
				t += 1
			if y1 != y2 and 1 <= y2 <= d and (y2 == int(y2)):
				t += 1
		except:
			break
	return t
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	nsols = 0
	for x in range(1, c + 1):
		discriminant = b ** 2 - 4 * x ** 2 + 4 * x * a
		if discriminant < 0:
			continue
		if discriminant > 0:
			yys = (b + discriminant ** 0.5, b - discriminant ** 0.5)
		else:
			yys = (b,)
		for yy in yys:
			if yy == int(yy) and 2 <= yy <= 2 * d:
				nsols += 1
	return nsols
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	if a == b == c == d:
		return 1
	else:
		cnt = 0
		for i in range(1, c + 1, 1):
			temp = b ** 2 - 4 * (i ** 2 - i * a)
			if temp < 0:
				pass
			else:
				p = temp
				z = int(temp ** (1 / 2))
				if z * z == math.ceil(p):
					s1 = (b + z) / 2
					s2 = (b - z) / 2
					if s1 >= 1 and s1 <= d:
						if math.ceil(s1) == (b + z) // 2:
							cnt = cnt + 1
					if s2 >= 1 and s2 <= d:
						if math.ceil(s2) == (b - z) // 2:
							cnt = cnt + 1
					if math.ceil(s2) == (b - z) // 2 == (b + z) // 2:
						cnt = cnt - 1
		return cnt
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def issquare(a):
	K = a ** 0.5
	K = int(K)
	if K ** 2 == a:
		return 1
	else:
		return 0

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		if 1 == 1:
			delta = b ** 2 - 4 * x ** 2 + 4 * a * x
			if delta >= 0:
				if issquare(delta) == 1:
					K = math.sqrt(delta)
					K = int(K)
					if K != 0:
						if (b + K) % 2 == 0:
							ans1 = (b - K) // 2
							ans2 = (b + K) // 2
							if ans1 > 0 and ans1 <= d:
								if x ** 2 + ans1 ** 2 - a * x - b * ans1 == 0:
									count += 1
							if ans2 > 0 and ans2 <= d:
								if x ** 2 + ans2 ** 2 - a * x - b * ans2 == 0:
									count += 1
					elif (b + K) % 2 == 0:
						ans1 = (b - K) // 2
						ans2 = (b + K) // 2
						if ans1 > 0 and ans1 <= d:
							if x ** 2 + ans1 ** 2 - a * x - b * ans1 == 0:
								count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from sys import stdin, stderr

def readInts():
	return map(int, stdin.readline().strip().split())

def print_err(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def sqrtN(n):
	if n < 0:
		return None
	x = n
	while x * x > n:
		x = (x + n // x) // 2
	if x * x < n:
		return None
	return x

def solve(a, b, c, d):
	out = 0
	for x in range(1, c + 1):
		rad = b * b - 4 * (x * x - x * a)
		sq = sqrtN(rad)
		if sq is None:
			continue
		vs = set()
		for v in [b + sq, b - sq]:
			if v % 2 == 0:
				v //= 2
				if v >= 1 and v <= d:
					vs.add(v)
		out += len(vs)
	return out

def run():
	(q,) = readInts()
	for _ in range(q):
		(a, b, c, d) = readInts()
		print(solve(a, b, c, d))
run()


import sys

def perfect(x):
	if x < 0:
		return 0
	c = int(x ** 0.5)
	if c * c == x:
		return c
	else:
		return 0

def countSolutions(a, b, c, d):
	res = 0
	for y in range(1, d + 1):
		d = a * a - 4 * (y * y - b * y)
		if d == 0:
			res += 1
		rd = perfect(d)
		if rd:
			x1 = a + rd
			if x1 % 2 == 0 and x1 >= 2 and (x1 <= 2 * c):
				res += 1
			x2 = a - rd
			if x2 % 2 == 0 and x2 >= 2 and (x2 <= 2 * c):
				res += 1
	return res
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from collections import defaultdict
for _ in range(int(input().strip())):
	(a, b, c, d) = [int(x) for x in input().strip().split(' ')]
	cnt = defaultdict(int)
	for x in range(1, c + 1):
		cnt[x * x - a * x] += 1
	ans = 0
	for y in range(1, d + 1):
		ans += cnt[b * y - y * y]
	print(ans)


import sys

def f1(l, i, a, b, d):
	if l == []:
		return 0
	else:
		y1 = l[0]
		y2 = l[1]
		ans = 0
		if l[0] >= 1 and l[0] <= d and (int(l[0]) == l[0]):
			if i * i + l[0] * l[0] == a * i + b * l[0]:
				ans += 1
		if l[1] >= 1 and l[1] <= d and (int(l[1]) == l[1]):
			if i * i + l[1] * l[1] == a * i + b * l[1]:
				ans += 1
		if y1 == y2 and ans == 2:
			return 1
		return ans

def sol(i, a, b):
	D = b * b - 4 * (i * i - a * i)
	if D < 0:
		return []
	D = D ** 0.5
	y1 = (D + b) / 2
	y2 = (b - D) / 2
	return [y1, y2]

def countSolutions(a, b, c, d):
	ans = 0
	for i in range(1, c + 1):
		l = sol(i, a, b)
		ans += f1(l, i, a, b, d)
	return ans
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		if b ** 2 - 4 * (x ** 2 - a * x) >= 0:
			y1 = (b + (b ** 2 - 4 * (x ** 2 - a * x)) ** 0.5) / 2
			y2 = (b - (b ** 2 - 4 * (x ** 2 - a * x)) ** 0.5) / 2
			if 1 <= y1 <= d and y1 % 1 == 0:
				count += 1
			if 1 <= y2 <= d and y2 % 1 == 0 and (y1 != y2):
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	c1 = a / 2
	c2 = b / 2
	r = ((a * a + b * b) / 4) ** 0.5
	x_min = int(math.ceil(max(1, c1 - r)))
	x_max = int(min(c, c1 + r))
	ans = 0
	for x in range(x_min, x_max + 1):
		if b ** 2 - 4 * x * x + 4 * a * x > 0:
			y1 = (b + (b ** 2 - 4 * x * x + 4 * a * x) ** 0.5) / 2
			if math.ceil(y1) == math.floor(y1) and y1 in range(1, d + 1):
				ans = ans + 1
			y2 = (b - (b ** 2 - 4 * x * x + 4 * a * x) ** 0.5) / 2
			if math.ceil(y2) == math.floor(y2) and y2 in range(1, d + 1):
				ans = ans + 1
		elif b ** 2 - 4 * x * x + 4 * a * x == 0:
			y1 = (b + (b ** 2 - 4 * x * x + 4 * a * x) ** 0.5) / 2
			if math.ceil(y1) == math.floor(y1) and y1 in range(1, d + 1):
				ans = ans + 1
	return ans
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from collections import defaultdict

def countSolutions(a, b, c, d):
	dd = defaultdict(int)
	for x in range(1, c + 1):
		val = x * (x - a)
		dd[val] += 1
	mysum = 0
	for y in range(1, d + 1):
		val = y * (b - y)
		mysum += dd[val]
	return mysum
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def countSolutions(a, b, c, d):
	sols = set()
	for x in range(1, c + 1):
		e2 = b * b + 4 * a * x - 4 * x * x
		if e2 < 0:
			continue
		e = int(sqrt(e2))
		if e * e == e2:
			if (b - e) % 2 == 0 and 1 <= (b - e) // 2 <= d:
				sols.add((x, (b - e) // 2))
			if (b + e) % 2 == 0 and 1 <= (b + e) // 2 <= d:
				sols.add((x, (b + e) // 2))
	return len(sols)
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	snum = 0
	for x in range(1, c + 1):
		discr = b ** 2 - 4 * x * (x - a)
		if discr < 0:
			break
		n = int(discr ** 0.5)
		if n ** 2 == discr:
			if (b + n) // 2 * 2 == b + n:
				y1 = (b - n) // 2
				y2 = (b + n) // 2
				if b > n:
					if n == 0:
						snum = snum + 1
					else:
						snum = snum + int(y1 <= d) + int(y2 <= d)
				else:
					snum = snum + int(y2 <= d)
	return snum
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		dis = b * b - 4 * (x * x - a * x)
		if dis >= 0:
			dis = pow(dis, 0.5)
			if dis == 0:
				if b % 2 == 0 and d >= b / 2 and (b / 2 >= 1):
					count += 1
					continue
			if dis == int(dis):
				if (b + dis) % 2 == 0 and d >= (b + dis) / 2 and ((b + dis) / 2 >= 1):
					count += 1
				if (b - dis) % 2 == 0 and d >= (b - dis) / 2 and ((b - dis) / 2 >= 1):
					count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		A = 1
		B = -b
		C = x * x - x * a
		delta = B * B - 4 * A * C
		if delta >= 0:
			delta = math.sqrt(delta)
			y0 = int(round((-B - delta) / (2 * A)))
			y1 = int(round((-B + delta) / (2 * A)))
			if 1 <= y0 <= d and y0 * y0 + x * x == x * a + y0 * b:
				count += 1
			if y1 != y0 and 1 <= y1 <= d and (y1 * y1 + x * x == x * a + y1 * b):
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for i in range(1, c + 1):
		if b * b - 4 * i * i + 4 * a * i > 0:
			x = math.sqrt(b * b - 4 * i * i + 4 * a * i)
			o = (b + x) / 2
			o1 = (b - x) / 2
			g = int(o)
			h = int(o1)
			if g == o and g >= 1 and (g <= d):
				count += 1
			if h == o1 and (h >= 1 and h <= d):
				count += 1
		elif b * b - 4 * i * i + 4 * a * i == 0:
			e = b / 2
			s = int(e)
			if s == e and s <= d and (s >= 1):
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from math import sqrt
Q = int(input())
for _ in range(Q):
	(A, B, C, D) = [int(x) for x in input().split()]
	solutions = 0
	for x in range(1, C + 1):
		(a, b, c) = (1, -B, x ** 2 - A * x)
		if b ** 2 - 4 * a * c < 0:
			continue
		elif b ** 2 - 4 * a * c == 0:
			if -b % 2 * a == 0:
				x1 = -b // 2 * a
				if x1 >= 1 and x1 <= D:
					solutions += 1
		else:
			if (-b + sqrt(b ** 2 - 4 * a * c)) % 2 * a == 0:
				x1 = (-b + sqrt(b ** 2 - 4 * a * c)) / 2 * a
				if x1 >= 1 and x1 <= D:
					solutions += 1
			if (-b - sqrt(b ** 2 - 4 * a * c)) % 2 * a == 0:
				x2 = (-b - sqrt(b ** 2 - 4 * a * c)) / 2 * a
				if x2 >= 1 and x2 <= D:
					solutions += 1
	print(solutions)


import math
q = int(input())
while q > 0:
	q -= 1
	(a, b, c, d) = input().split()
	a = int(a)
	b = int(b)
	c = int(c)
	d = int(d)
	cnt = 0
	sq = a * a + b * b
	for x in range(1, c + 1, 1):
		ysq = sq - (2 * x - a) * (2 * x - a)
		if ysq < 0:
			continue
		y = int(math.sqrt(ysq))
		if y * y != ysq:
			continue
		if (y + b) % 2:
			continue
		y1 = (y + b) / 2
		if y1 >= 1 and y1 <= d:
			cnt += 1
		y2 = (b - y) / 2
		if y2 >= 1 and y2 <= d and (y1 != y2):
			cnt += 1
	print(cnt)


import sys
import math

def countSolutions(a, b, c, d):
	sols = 0
	for i in range(1, c + 1):
		egz = b * b - 4 * (i * i - i * a)
		if egz >= 0:
			s1 = b + math.sqrt(egz)
			if s1 % 2 == 0 and s1 / 2 > 0 and (int(s1 / 2) < d + 1):
				sols += 1
			s2 = b - math.sqrt(egz)
			if s2 % 2 == 0 and s2 / 2 > 0 and (int(s2 / 2) < d + 1) and (int(s1 / 2) != int(s2 / 2)):
				sols += 1
	return sols
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import floor, sqrt

def countSolutions(a, b, c, d):
	count = 0
	k = floor((a + sqrt(a ** 2 + b ** 2)) / 2)
	if k <= c:
		c = k
	for x in range(1, c + 1):
		y1 = sqrt((a ** 2 + b ** 2) / 4 - (x - a / 2) ** 2) + b / 2
		y2 = b / 2 - sqrt((a ** 2 + b ** 2) / 4 - (x - a / 2) ** 2)
		u = v = 1
		if y1 == floor(y1) and y1 <= d and (y1 >= 1):
			count += 1
			u = 0
		if y2 == floor(y2) and y2 <= d and (y2 >= 1):
			count += 1
			v = 0
		if floor(y1) == floor(y2) and u == 0 and (v == 0):
			count -= 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	countsoln = 0
	for x in range(1, c + 1):
		discr = b * b - 4 * (x * x - a * x)
		if discr == 0:
			yp = b / 2
			if int(yp) == yp and yp >= 1 and (yp <= d):
				countsoln += 1
		elif discr > 0:
			rtd = int(discr ** 0.5)
			if rtd ** 2 == discr:
				yp = (b - rtd) / 2
				if int(yp) == yp:
					if yp >= 1 and yp <= d:
						countsoln += 1
					yp = (b + rtd) / 2
					if yp >= 1 and yp <= d:
						countsoln += 1
	return countsoln
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		const = x * (x - a)
		if b * b - 4 * const == 0:
			root = (b + math.sqrt(b * b - 4 * const)) / 2
			if root == int(root) and d >= root > 0:
				count += 1
		elif b * b - 4 * const > 0:
			root = (b + math.sqrt(b * b - 4 * const)) / 2
			if root == int(root) and d >= root > 0:
				count += 1
			root = (b - math.sqrt(b * b - 4 * const)) / 2
			if root == int(root) and d >= root > 0:
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys

def countSolutions(a, b, c, d):
	res = 0
	if c < d:
		for x in range(1, c + 1):
			aux = x ** 2 - a * x
			if x < a or (x >= a and aux <= (b / 2) ** 2):
				y = b / 2 + ((b / 2) ** 2 - aux) ** (1 / 2)
				if y == int(y) and y <= d:
					res += 1
				if x > a and aux < (b / 2) ** 2:
					y = b / 2 - ((b / 2) ** 2 - aux) ** (1 / 2)
					if y == int(y) and y <= d:
						res += 1
	else:
		for y in range(1, d + 1):
			aux = y ** 2 - b * y
			if y < b or (y >= b and aux <= (a / 2) ** 2):
				x = a / 2 + ((a / 2) ** 2 - aux) ** (1 / 2)
				if x == int(x) and x <= c:
					res += 1
				if y > b and aux < (a / 2) ** 2:
					x = a / 2 - ((a / 2) ** 2 - aux) ** (1 / 2)
					if x == int(x) and x <= c:
						res += 1
	return res
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import *

def countSolutions(a, b, c, d):
	s = 0
	for x in range(1, c + 1):
		delta = b * b - 4 * (x * x - x * a)
		if delta == 0:
			y = b / 2
			if int(y) == y and y <= d and (y >= 1):
				s += 1
		if delta > 0:
			y1 = (b + sqrt(delta)) / 2
			y2 = (b - sqrt(delta)) / 2
			if int(y1) == y1 and y1 <= d and (y1 >= 1):
				s += 1
			if int(y2) == y2 and y2 <= d and (y2 >= 1):
				s += 1
	return s
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):

	def check_result(y):
		if y > 0 and y <= d and (y % 1 == 0):
			return 1
		return 0
	counter = 0
	for x in range(1, c + 1):
		D = b ** 2 - 4 * (x ** 2 - a * x)
		if D == 0:
			D_sqrt = math.sqrt(D)
			counter += check_result(b / 2)
		elif D > 0:
			D_sqrt = math.sqrt(D)
			counter += check_result((b + D_sqrt) / 2)
			counter += check_result((b - D_sqrt) / 2)
		else:
			break
	return counter
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys, math
E = 1e-06
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = 0
	for y in range(1, d + 1):
		B = -a
		C = y * y - b * y
		d2 = B * B - 4 * C
		if d2 < 0:
			continue
		d = math.sqrt(d2)
		x1 = (-B + d) / 2
		if abs(x1 - int(x1)) < E and x1 >= 1 and (x1 <= c):
			result += 1
		if abs(d) < E:
			continue
		x2 = (-B - d) / 2
		if abs(x2 - int(x2)) < E and x2 >= 1 and (x2 <= c):
			result += 1
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		p = b ** 2 - 4 * (x ** 2 - x * a)
		if p >= 0:
			m = (b + math.sqrt(p)) / 2
			n = (b - math.sqrt(p)) / 2
			if m != n:
				if round(m) == m and m <= d and (m >= 1):
					count += 1
				if round(n) == n and n <= d and (n >= 1):
					count += 1
			elif round(m) == m and m <= d and (m >= 1):
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
fnds = {}

def checkFound(x, y, a, b):
	y = int(y)
	tup = str(a) + '_' + str(x) + '_' + str(b) + '_' + str(y)
	if tup in fnds:
		return 1
	else:
		return 0

def addFound(x, y, a, b):
	y = int(y)
	tup = str(a) + '_' + str(x) + '_' + str(b) + '_' + str(y)
	tup2 = str(b) + '_' + str(y) + '_' + str(a) + '_' + str(x)
	fnds[tup] = 1
	fnds[tup2] = 1

def countSolutions(a, b, c, d):
	count = 0
	lastCount = 0
	for x in range(1, c + 1):
		m = x * x - x * a
		l = -b
		if l * l < 4 * m:
			continue
		sq1 = (-l + (l * l - 4 * m) ** (1 / 2) // 1) / 2
		sq2 = (-l - (l * l - 4 * m) ** (1 / 2) // 1) / 2
		if sq1 > 0 and sq1 == sq1 // 1 and (sq1 <= d) and (checkFound(x, sq1, a, b) == 0) and (x * x + sq1 * sq1 == x * a + sq1 * b):
			sq1 = int(sq1)
			count += 1
			addFound(x, sq1, a, b)
			if a == b and x != sq1 and (x <= d) and (sq1 <= c):
				count += 1
		if sq2 > 0 and sq2 == sq2 // 1 and (sq1 != sq2) and (sq2 <= d) and (checkFound(x, sq2, a, b) == 0) and (x * x + sq2 * sq2 == x * a + sq2 * b):
			sq2 = int(sq2)
			count += 1
			addFound(x, sq2, a, b)
			if a == b and x != sq2 and (x <= d) and (sq2 <= c):
				count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	fnds = {}
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	if a != b:
		result += countSolutions(b, a, d, c)
	print(result)


import sys, math

def countSolutions(a, b, c, d):
	i = 0
	for x in range(1, c + 1):
		try:
			y = (b + math.sqrt(b * b - 4 * x * x + 4 * x * a)) / 2
		except:
			y = 0
		try:
			y2 = (b - math.sqrt(b * b - 4 * x * x + 4 * x * a)) / 2
		except:
			y2 = 0
		if y % 1 == 0 and 1 <= y <= d:
			i += 1
		if y2 % 1 == 0 and 1 <= y2 <= d and (y2 != y):
			i += 1
	return i
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		if b ** 2 - 4 * x ** 2 + 4 * a * x >= 0:
			y1 = b / 2 + math.sqrt(b ** 2 - 4 * x ** 2 + 4 * a * x) / 2
			y2 = b / 2 - math.sqrt(b ** 2 - 4 * x ** 2 + 4 * a * x) / 2
			if math.floor(y1) == math.ceil(y1) == y1 and 1 <= y1 <= d and (y1 != y2):
				count = count + 1
			if math.floor(y2) == math.ceil(y2) == y2 and 1 <= y2 <= d and (y1 != y2):
				count = count + 1
			if math.floor(y2) == math.ceil(y2) == y2 and 1 <= y2 <= d and (math.floor(y1) == math.ceil(y1) == y1) and (1 <= y1 <= d) and (y1 == y2):
				count = count + 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


from math import sqrt
t = int(input())
for i in range(t):
	(a, b, c, d) = map(int, input().split())
	count = 0
	for x in range(1, c + 1):
		D = b * b - 4 * (x - a) * x
		if D % 1 == 0 and D >= 0:
			y1 = (b + sqrt(D)) / 2
			y2 = (b - sqrt(D)) / 2
			if D > 0:
				if y1 % 1 == 0 and y1 <= d and (y1 > 0):
					count += 1
				if y2 % 1 == 0 and y2 <= d and (y2 > 0):
					count += 1
			if D == 0:
				if b / 2 % 1 == 0:
					count += 1
	print(count)


from math import sqrt
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	count = 0
	b_2 = b / 2
	b2_4 = b * b / 4
	for x in range(1, c + 1):
		try:
			root = sqrt(a * x - x * x + b2_4)
			y1 = root + b_2
			y2 = -root + b_2
			if y1.is_integer() and 1 <= y1 <= d:
				count += 1
			if y2.is_integer() and 1 <= y2 <= d and (y1 != y2):
				count += 1
		except ValueError:
			pass
	print(count)


import sys
from math import sqrt, isclose

def quad(x):
	d2 = b * b - 4 * x * (x - a)
	if d2 < 0:
		return 0
	if d2 > 0:
		ds = sqrt(d2)
		rds = round(ds)
		if isclose(ds, rds, abs_tol=1e-05) and rds % 2 == b % 2:
			s1 = (b - rds) // 2
			ct = int(1 <= s1 <= d)
			s2 = (b + rds) // 2
			ct += int(1 <= s2 <= d)
			return ct
		return 0
	return 1

def countSolutions(a, b, c, d):
	ct = 0
	for x in range(1, c + 1):
		ct += quad(x)
	return ct
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
import math
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	count = 0
	for y in range(1, d + 1):
		D = a * a / 4 - y * (y - b)
		if D >= 0:
			x1 = a / 2 + math.sqrt(D)
			x2 = a / 2 - math.sqrt(D)
			if x1 == int(x1):
				if x1 >= 1 and x1 <= c:
					count = count + 1
			if x2 == int(x2) and x1 != x2:
				if x2 >= 1 and x2 <= c:
					count = count + 1
	print(count)


import sys
from math import sqrt, ceil

def countSolutions(a, b, c, d):
	ans = 0
	radius_squared = (a ** 2 + b ** 2) / 4
	if c == a and d == b:
		return 1
	elif c < a and d < b:
		return 0
	else:
		for x in range(1, c + 1):
			x_term = radius_squared - (x - a / 2) ** 2
			if x_term >= 0:
				y1 = b / 2 + sqrt(x_term)
				y2 = b / 2 - sqrt(x_term)
				if y1 == y2 and y1.is_integer() and (y1 >= 1) and (y1 <= d):
					ans += 1
				else:
					if y1.is_integer() and y1 <= d and (y1 >= 1):
						ans += 1
					if y2.is_integer() and y2 <= d and (y2 >= 1):
						ans += 1
		return ans
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import sys
for q in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	count = 0
	for y in range(1, d + 1):
		err = 0
		r = a * a + 4 * y * (b - y)
		if r < 0:
			break
		x1 = 0.5 * (a - r ** 0.5)
		x2 = 0.5 * (a + r ** 0.5)
		if x1.is_integer() and 1 <= x1 <= c:
			count += 1
		if x2.is_integer() and 1 <= x2 <= c and (x1 != x2):
			count += 1
	print(count)


import sys
import math

def countSolutions(a, b, c, d):
	nsol = 0
	for x in range(1, c + 1):
		D = b ** 2 - 4 * (x ** 2 - a * x)
		if D > 0:
			y = (b + math.sqrt(D)) / 2
			if y.is_integer() and 1 <= y <= d:
				nsol += 1
			y = (b - math.sqrt(D)) / 2
			if y.is_integer() and 1 <= y <= d:
				nsol += 1
		elif D == 0:
			y = b / 2
			if y.is_integer() and 1 <= y <= d:
				nsol += 1
		elif x > a:
			break
	return nsol
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math

def countSolutions(a, b, c, d):
	count = 0
	xc = a / 2
	yc = b / 2
	r2 = (a ** 2 + b ** 2) / 4
	r = math.sqrt(r2)
	ymin = max(1, int(math.ceil(yc - r)))
	ymax = min(d, int(math.floor(yc + r)))
	for y in range(ymin, ymax + 1):
		v2 = (y - yc) ** 2
		u = (r2 - v2) ** 0.5
		xp = xc + u
		xm = xc - u
		count += int(1 <= xp <= c and int(xp) == xp)
		count += int(1 <= xm <= c and int(xm) == xm and (not xm == xp))
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = [int(i) for i in input().strip().split()]
	result = countSolutions(a, b, c, d)
	print(result)


import math

def countSolutions(a, b, c, d):
	count = 0
	for x in range(1, c + 1):
		det = b ** 2 - 4 * (x ** 2 - a * x)
		if det < 0:
			continue
		det = math.sqrt(det)
		plus_y = (b + det) / 2
		mins_y = (b - det) / 2
		if math.floor(plus_y) == plus_y and plus_y <= d and (plus_y >= 1):
			count += 1
		if math.floor(mins_y) == mins_y and mins_y <= d and (mins_y >= 1) and (plus_y != mins_y):
			count += 1
	return count
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	count = 0
	for x in range(1, c + 1):
		D = b * b + 4 * a * x - 4 * x * x
		if D >= 0:
			p = math.sqrt(D)
			q = int(math.sqrt(D))
			if p == q:
				if (q + b) % 2 == 0 and (q + b) // 2 <= d:
					count = count + 1
				if b - q > 0 and (b - q) % 2 == 0 and ((b - q) // 2 < d) and (D != 0):
					count = count + 1
	print(count)


import sys
import math

def countSolutions(a, b, c, d):
	count = 0
	a1 = 1
	b1 = -b
	dt = 0
	for i in range(1, c + 1, 1):
		c1 = i * i - i * a
		d1 = b1 * b1 - 4 * a1 * c1
		if d1 < 0:
			continue
		dt = math.sqrt(b1 * b1 - 4 * a1 * c1)
		pqr = dt - int(dt)
		if pqr != 0.0:
			continue
		sol1 = (-b1 - dt) / 2 * a1
		sol2 = (-b1 + dt) / 2 * a1
		ll = 0
		rr = 0
		if sol1 > d or sol1 < 1:
			ll = 1
		if sol2 > d or sol2 < 1:
			rr = 1
		if sol1 == sol2 and rr == 0 and (ll == 0):
			count += 1
			continue
		sol1 = sol1 - int(sol1)
		sol2 = sol2 - int(sol2)
		if sol1 == 0.0 and ll == 0:
			count += 1
		if sol2 == 0.0 and rr == 0:
			count += 1
	print(count)
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	countSolutions(a, b, c, d)


import math
import sys

def countSolutions(p, q, r, s):
	flag = 0
	for i in range(1, r + 1):
		ans = p * p + q * q - (2 * i - p) ** 2
		if ans < 0:
			break
		f = math.sqrt(ans)
		if int(f) != f:
			continue
		val1 = int((q + f) / 2)
		val2 = int((q - f) / 2)
		if val1 >= 1 and val1 <= s:
			flag += 1
		if val2 >= 1 and val2 <= s:
			flag += 1
		if val1 == val2:
			flag -= 1
	return flag
q = int(input().strip())
for a0 in range(q):
	(p, q, r, s) = input().strip().split(' ')
	(p, q, r, s) = [int(p), int(q), int(r), int(s)]
	res = countSolutions(p, q, r, s)
	print(res)


import sys

def countSolutions(a, b, c, d):
	s = []
	t = []
	if c > d:
		for x in range(1, d + 1):
			s.append(x ** 2 - x * a)
			t.append(x * b - x ** 2)
		for x in range(d + 2, c + 1):
			s.append(x ** 2 - x * a)
	else:
		for x in range(1, c + 1):
			s.append(x ** 2 - x * a)
			t.append(x * b - x ** 2)
		for x in range(c + 2, d + 1):
			t.append(x * b - x ** 2)
	l = set(s)
	g = set(t)
	h = l & g
	count = 0
	f = list(h)
	for i in range(0, len(f)):
		j = s.count(f[i])
		k = t.count(f[i])
		count += j * k
	return count
q = int(input())
for r in range(0, q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = (int(a), int(b), int(c), int(d))
	result = countSolutions(a, b, c, d)
	print(result)


import sys
from math import sqrt

def countSolutions(a, b, c, d):
	tot = 0
	q = (a * a + b * b) / 4
	for i in range(1, c + 1):
		try:
			k = sqrt(q - (i - a / 2) ** 2)
		except:
			continue
		if (b / 2 + k).is_integer():
			if int(b / 2 + k) < d + 1:
				if k != 0:
					tot += 1
		if (b / 2 - k).is_integer():
			if int(b / 2 - k) < d + 1 and int(b / 2 - k) > 0:
				tot += 1
	return tot
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)


import math
for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split(' '))
	count = 0
	for x in range(1, c + 1):
		delta = b * b + 4 * a * x - 4 * x * x
		if delta < 0:
			break
		if delta == 0 and b % 2 == 0 and (1 <= b // 2 <= d):
			count += 1
			continue
		sqrt = math.sqrt(delta)
		if abs(sqrt - math.floor(sqrt)) < 1e-07 and (b + sqrt) % 2 == 0:
			if 1 <= (b + sqrt) / 2 <= d:
				count += 1
			if 1 <= (b - sqrt) / 2 <= d:
				count += 1
	print(count)


def hasRoot(a, b, c, mi, mx):
	sq = b * b - 4 * a * c
	if sq < 0:
		return 0
	sqroot = int(sq ** 0.5)
	if sqroot ** 2 != sq:
		return 0
	if (b + sqroot) % (2 * a) != 0:
		return 0
	ret = 0
	root = (-b - sqroot) / (2 * a)
	if root >= mi and root <= mx:
		ret += 1
	root = (-b + sqroot) / (2 * a)
	if sqroot != 0 and root >= mi and (root <= mx):
		ret += 1
	return ret
for _ in range(int(input())):
	res = 0
	(a, b, c, d) = map(int, input().split())
	for x in range(1, c + 1):
		res += hasRoot(1, -b, x ** 2 - a * x, 1, d)
	print(res)


from math import sqrt

def countSolutions(a, b, c, d):
	counter = 0
	for x in range(1, c + 1):
		D = 4 * a * x + b ** 2 - 4 * x ** 2
		if D < 0:
			continue
		aa = sqrt(D)
		(y, rem) = divmod(b - aa, 2)
		(y2, rem2) = divmod(aa + b, 2)
		if rem == 0 and 1 <= y <= d:
			counter += 1
		if rem2 == 0 and 1 <= y2 <= d and (y != y2):
			counter += 1
	return counter
q = int(input().strip())
for a0 in range(q):
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	result = countSolutions(a, b, c, d)
	print(result)