Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Today, Chef was trying to solve a problem he found pretty hard: Given an integer N and a triple of integers (a, b, c), compute the number of triples of positive integers (x, y, z) such that N = x · y · z, x ≤ a, y ≤ b and z ≤ c.

Can you help Chef solve this problem?

Two triples (x_{1}, y_{1}, z_{1}) and (x_{2}, y_{2}, z_{2}) differ if x_{1} is not equal to x_{2} or y_{1} is not equal to y_{2} or z_{1} is not equal to z_{2}.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains four space-separated integers N, a, b and c.

------ Output ------ 

For each test case, print a single line containing one integer — the number of valid triples (x, y, z).

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

$1 ≤ T ≤ 20$
$1 ≤ N ≤ 10^{9}$
$1 ≤ a, b, c ≤ 10^{6}$

----- Sample Input 1 ------ 
3
100 8 23 11
497296800 1000000 1000000 1000000
1 1 2 3
----- Sample Output 1 ------ 
10
97800
1
----- explanation 1 ------ 
Example case 1: There are 10 valid triples (x, y, z): (1, 10, 10), (1, 20, 5), (2, 5, 10), (2, 10, 5), (4, 5, 5), (5, 2, 10), (5, 4, 5), (5, 5, 4), (5, 10, 2), (5, 20, 1).

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def divisor(num):
	a = ()
	div = list(a)
	i = 1
	while i * i < num:
		if num % i == 0:
			div.append(i)
			div.append(num // i)
		i += 1
	if i * i == num:
		div.append(i)
	return div
test = int(input())
while test:
	(n, a, b, c) = map(int, input().split())
	d = divisor(n)
	ct = 0
	for i in d:
		if i <= a:
			for j in d:
				if j <= b:
					if n % (i * j) == 0 and n // (i * j) <= c:
						ct += 1
	print(ct)
	test -= 1


from collections import *
from itertools import *
q = defaultdict(set)

def divc(i):
	for j in range(1, int(i ** 0.5) + 1):
		if i % j == 0:
			q[i].add(j)
			q[i].add(i // j)

def cnt(i, j):
	ans = 0
	for k in q[j]:
		o = j // k
		for (x, y, z) in per:
			if i <= x and k <= y and (o <= z):
				ans += 1
	return ans
for _ in range(int(input())):
	(n, a, b, c) = map(int, input().split())
	per = set(permutations([a, b, c], 3))
	l = set()
	for j in range(1, int(n ** 0.5) + 1):
		if n % j == 0:
			if j not in q:
				divc(j)
			if n // j not in q:
				divc(n // j)
			l.add(j)
			l.add(n // j)
	ans = 0
	for i in l:
		ans += cnt(i, n // i)
	print(ans // [0, 1, 2, 6][len({a, b, c})])


import math
t = int(input())
for i in range(t):
	(n, a, b, c) = map(int, input().split())
	s = 0
	d = [1]
	k = 2
	while k <= math.sqrt(n):
		if n % k == 0:
			if n // k == k:
				d.append(k)
			else:
				d.append(k)
				d.append(n // k)
		k += 1
	d.sort()
	for x in d:
		if x <= a:
			for y in d:
				if y <= b:
					if n % (x * y) == 0 and n // (x * y) <= c:
						s += 1
				else:
					break
		else:
			break
	print(s)


import math
for tc in range(int(input())):
	(n, a, b, c) = map(int, input().split(' '))
	count = 0
	div = [1]
	i = 2
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				div.append(i)
			else:
				div.append(i)
				div.append(n // i)
		i += 1
	div.sort()
	for x in div:
		if x <= a:
			for y in div:
				if y <= b:
					if n % (x * y) == 0 and n // (x * y) <= c:
						count += 1
				else:
					break
		else:
			break
	print(count)


import math
for _ in range(int(input())):
	(n, a, b, c) = map(int, input().split())
	div = [1]
	i = 2
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				div.append(i)
			else:
				div.extend([i, n // i])
		i += 1
	div.sort()
	cnt = 0
	for i in div:
		if i <= a:
			for j in div:
				if j <= b:
					if n % (i * j) == 0 and n // (i * j) <= c:
						cnt += 1
				else:
					break
		else:
			break
	print(cnt)


from math import sqrt
t = int(input())
for i in range(t):
	l1 = [int(i) for i in input().split()]
	n = l1[0]
	l1.pop(0)
	if n == 1:
		print(1)
	else:
		(a, c) = (min(l1), max(l1))
		b = sum(l1) - a - c
		seta = set()
		setb = set()
		upper = min(b + 1, int(sqrt(n)) + 1)
		for i in range(1, upper):
			if n % i == 0:
				(n1, n2) = (i, n // i)
				if n1 < a:
					seta.add(n1)
				if n1 < b:
					setb.add(n1)
				if n2 < a:
					seta.add(n2)
				if n2 < b:
					setb.add(n2)
		count = 0
		for i in seta:
			for j in setb:
				if n % (i * j) == 0 and n // (i * j) < c:
					count += 1
		print(count)


import math

def findDiv(n):
	i = 1
	div = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				div.append(i)
			else:
				div.append(i)
				div.append(n // i)
		i += 1
	return div
t = int(input())
for _ in range(t):
	(n, a, b, c) = [int(s) for s in input().split(' ')]
	div = findDiv(n)
	x = [ele for ele in div if ele <= a]
	y = [ele for ele in div if ele <= b]
	cnt = 0
	for xVal in x:
		for yVal in y:
			mod = n % (xVal * yVal)
			if mod == 0 and n // (xVal * yVal) <= c:
				cnt += 1
	print(cnt)


from math import *
for j in range(int(input())):
	(n, a, b, c) = map(int, input().split())
	x = [1]
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			if n // i == i:
				x.append(i)
			else:
				x.append(n // i)
				x.append(i)
	am = 0
	for i in x:
		if i <= a:
			for j in x:
				if j <= b:
					if n % (i * j) == 0:
						if n // (i * j) <= c:
							am += 1
	print(am)


import math
t = int(input())
for i in range(t):
	(N, a, b, c) = map(int, input().split())
	l1 = [1]
	l2 = [1]
	for j in range(2, int(math.sqrt(N)) + 1):
		if N % j == 0:
			if N // j == j:
				if j <= a:
					l1.append(j)
				if j <= b:
					l2.append(j)
			else:
				if j <= a:
					l1.append(j)
				if N // j <= a:
					l1.append(N // j)
				if j <= b:
					l2.append(j)
				if N // j <= b:
					l2.append(N // j)
	count = 0
	for i in l1:
		if N % i == 0:
			q = N // i
			for j in l2:
				if q % j == 0:
					z = q // j
					if z <= c:
						count += 1
	print(count)


from math import sqrt
t = int(input())
for test in range(t):
	(n, a, b, c) = map(int, input().split())
	l1 = [1]
	l2 = [1]
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			if n // i == i:
				if i <= a:
					l1.append(i)
				if i <= b:
					l2.append(i)
			else:
				if i <= a:
					l1.append(i)
				if i <= b:
					l2.append(i)
				if n // i <= a:
					l1.append(n // i)
				if n // i <= b:
					l2.append(n // i)
	counter = 0
	for i in l1:
		if n % i == 0:
			p = n // i
			for j in l2:
				if p % j == 0:
					z = p // j
					if z <= c:
						counter += 1
	print(counter)


import math

def fcts(n):
	s = set()
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	return sorted(list(set(s)))
for _ in range(int(input())):
	(n, a, b, c) = map(int, input().split())
	l = fcts(n)
	cc = 0
	for i in range(len(l)):
		if l[i] <= a:
			newli = fcts(n // l[i])
			newnum = n // l[i]
			for j in range(len(newli)):
				if newli[j] <= b and newnum // newli[j] <= c:
					cc += 1
	print(cc)


import math

def Divisors(n, l):
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
		i = i + 1
t = int(input())
for _ in range(t):
	(n, a, b, c) = map(int, input().strip().split())
	la = []
	lb = []
	lc = []
	l = []
	Divisors(n, l)
	for i in l:
		if i <= a:
			la.append(i)
		if i <= b:
			lb.append(i)
		if i <= c:
			lc.append(i)
	la = sorted(la)
	lb = sorted(lb)
	lc = sorted(lc)
	dict_c = {}
	for i in lc:
		dict_c[i] = 1
	cnt = 0
	for i in la:
		for j in lb:
			if n % (i * j) == 0:
				if dict_c.get(n // (i * j)) != None:
					cnt += 1
	print(cnt)


from math import sqrt
x = int(input())
for __ in range(x):
	(n, a, b, c) = map(int, input().split())
	lol = [1]
	yo = [1]
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			if n // i == i:
				if i <= a:
					lol.append(i)
				if i <= b:
					yo.append(i)
			else:
				if i <= a:
					lol.append(i)
				if i <= b:
					yo.append(i)
				if n // i <= a:
					lol.append(n // i)
				if n // i <= b:
					yo.append(n // i)
	k = 0
	for i in lol:
		if n % i == 0:
			l = n // i
			for j in yo:
				if l % j == 0:
					zo = l // j
					if zo <= c:
						k += 1
	print(k)


for t in range(int(input())):
	(n, a, b, c) = map(int, input().split())
	factors = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			factors.append(i)
			if i * i != n:
				factors.append(n // i)
	factors.sort()
	count = 0
	for i in factors:
		if i <= a:
			rem = n // i
			for j in factors:
				if j <= b and rem % j == 0:
					if rem // j <= c:
						count += 1
	print(count)


import math
from functools import reduce

def factors(n, l):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(pow(n, 0.5) + 1)) if n % i == 0 and i <= max(l))))
t = int(input())
for i in range(t):
	k = 0
	(n, a, b, c) = [int(x) for x in input().split()]
	l = [a, b, c]
	ar = list(factors(n, l))
	k = 0
	for i in ar:
		if n % i == 0 and i <= a:
			p = int(n / i)
			for j in ar:
				if p % j == 0 and j <= b:
					if int(p / j) <= c:
						k += 1
	print(k)


t = int(input())
while t > 0:
	string = input().split()
	n = int(string[0])
	a = int(string[1])
	b = int(string[2])
	c = int(string[3])
	ans = 0
	factor = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			factor.append(i)
			if n // i != i:
				factor.append(n // i)
	factor.sort()
	for i in factor:
		if i <= a:
			rem = n // i
			for j in factor:
				if rem % j == 0 and j <= b:
					if rem // j <= c:
						ans += 1
	print(ans)
	t -= 1


from functools import reduce

def factorial(n, m):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1, 2 if n % 2 else 1) if n % i == 0 if i <= m)))
for T in range(int(input())):
	(N, a, b, c) = map(int, input().split())
	count = 0
	factors = sorted(factorial(N, max(a, b, c)))
	for x in factors:
		if x > N:
			break
		if x > a:
			break
		for y in factors:
			if y > N:
				break
			if y > b:
				break
			z = x * y
			if z > N:
				break
			if N % z == 0 and N // z <= c:
				count += 1
	print(count)


def fact(arg, m):
	result = set([1])
	for i in range(1, int(arg ** 0.5) + 1):
		if arg % i == 0:
			result.add(i)
			if int(arg / i) <= m:
				result.add(int(arg / i))
	return result
for i in range(int(input())):
	(N, a, b, c) = input().split()
	N = int(N)
	a = int(a)
	b = int(b)
	c = int(c)
	dummy = sorted(fact(N, max(a, b, c)))
	l1 = sorted(list((x for x in dummy if x <= a)))
	l2 = sorted(list((x for x in dummy if x <= b)))
	count = 0
	for x in l1:
		for y in l2:
			z = x * y
			if z > N:
				break
			if N % z == 0 and N // z <= c:
				count += 1
	print(count)


from math import *
t = int(input())
for a0 in range(t):
	count = 0
	(n, a, b, c) = input().split()
	(n, a, b, c) = [int(n), int(a), int(b), int(c)]
	k = sqrt(n)
	k = int(k)
	arr = []
	for i in range(1, k + 1):
		if n % i == 0:
			arr.append(i)
			if n // i != i:
				arr.append(n // i)
	count = 0
	for i in arr:
		if i <= a:
			x = n / i
			for j in arr:
				if x % j == 0 and j <= b:
					y = x / j
					if y <= c:
						count += 1
	print(count)


import math

def fact(n):
	factors = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			factors.append(i)
			if not n // i == i:
				factors.append(n // i)
	return factors
t = int(input())
ans = []
while t > 0:
	t -= 1
	(n, a, b, c) = map(int, input().split())
	count = 0
	factors = fact(n)
	count = 0
	for i in factors:
		if i <= a:
			r = n // i
			for j in factors:
				if r % j == 0 and j <= b:
					s = r // j
					if s <= c:
						count += 1
	ans.append(count)
print('\n'.join(map(str, ans)))


def fact(n):
	k = 0
	a = []
	for i in range(1, int(n ** (1 / 2)) + 2):
		if n % i == 0 and i not in a:
			if i != int(n / i):
				k += 2
				a.append(i)
				a.append(int(n / i))
			else:
				k += 1
				a.append(i)
	return a
t = int(input())
while t > 0:
	(n, a, b, c) = list(map(int, input().split()))
	k = 0
	li = fact(n)
	for i in li:
		if n % i == 0 and i <= a:
			p = n // i
			for j in li:
				if p % j == 0 and j <= b:
					if p // j <= c:
						k += 1
	print(k)
	t -= 1


import math

def findfact(n, l):
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0 and i not in l:
			if n / i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(int(int(n) / int(i)))
t = int(input())
for c in range(t):
	(n, a, b, c) = [int(p) for p in input().split()]
	l = []
	findfact(n, l)
	count = 0
	dontgo = 0
	if n == 1 and a > 0 and (b > 0) and (c > 0):
		print('1')
	else:
		for j in range(0, len(l)):
			if l[j] <= a:
				k = int(n / l[j])
				for i in range(0, len(l)):
					if k % l[i] == 0 and int(int(n) / int(l[i] * l[j])) <= c and (l[i] <= b):
						count += 1
		print(count)


from math import floor, sqrt

def eratosthenes(n):
	is_comp = bytearray((n - 1) // 2)
	for p in range(3, floor(sqrt(n)) + 1, 2):
		if is_comp[(p - 3) // 2]:
			continue
		is_comp[(p ** 2 - 3) // 2::p] = b'\x01' * ((n - p ** 2) // (2 * p) + 1)
	return [2] + [2 * i + 3 for i in range((n - 1) // 2) if not is_comp[i]]
primes = eratosthenes(10 ** 5)

def factorize(N):
	if N == 1:
		return []
	facts = []
	for p in primes:
		if N % p == 0:
			m = 1
			N //= p
			while N % p == 0:
				m += 1
				N //= p
			facts.append((p, m))
			if N == 1:
				return facts
		elif p ** 2 > N:
			return facts + [(N, 1)]

def solve_part(rem, M, bound1, bound2):
	divs = [1]
	for p in rem:
		m = rem[p]
		divs += [d * p ** i for i in range(1, m + 1) for d in divs if d * p ** i <= bound1]
	count = 0
	for d in divs:
		if d * bound2 >= M:
			count += 1
	return count

def solve(N, a, b, c):
	res = 0
	facts = factorize(N)
	divs = [(1, tuple())]
	for (p, m) in facts:
		divs = [(r * p ** i, t + ((p, i),)) for (r, t) in divs for i in range(1, m + 1) if r * p ** i <= a] + divs
	for (d, t) in divs:
		rem = {facts[i][0]: facts[i][1] for i in range(len(facts))}
		for (p, m) in t:
			rem[p] -= m
			if rem[p] == 0:
				del rem[p]
		res += solve_part(rem, N // d, b, c)
	return res
T = int(input())
for query in range(T):
	(N, a, b, c) = [int(v) for v in input().split()]
	(a, b, c) = sorted([a, b, c])
	print(solve(N, a, b, c))


def fact(n):
	A = []
	for i in range(1, int(pow(n, 1 / 2)) + 1):
		if n % i == 0 and i not in A:
			A.append(i)
			if i != n // i:
				A.append(n // i)
	return A
for _ in range(int(input())):
	(N, a, b, c) = [int(x) for x in input().split()]
	L = fact(N)
	k = 0
	for i in range(len(L)):
		if N % L[i] == 0 and L[i] <= a:
			p = N // L[i]
			for j in range(len(L)):
				if p % L[j] == 0 and L[j] <= b:
					if p // L[j] <= c:
						k += 1
	print(k)


import math as m

def fact(n):
	a = []
	for i in range(1, int(n ** (1 / 2)) + 2):
		if n % i == 0 and i not in a:
			if i != n // i:
				a.append(i)
				a.append(n // i)
			else:
				a.append(i)
	return a
t = int(input())
for i in range(0, t):
	(N, a, b, c) = map(int, input().split())
	arr = fact(N)
	k = 0
	for i in arr:
		if i <= a:
			p = N // i
			for j in arr:
				if p % j == 0 and j <= b:
					if p // j <= c:
						k += 1
	print(k)


import math

def tryComb(a, b, c, x, y, z):
	res = 0
	if a < x and b < y and (c < z):
		res += 1
	if a < x and b < z and (c < y):
		res += 1
	if a < y and b < x and (c < z):
		res += 1
	if a < y and b < z and (c < x):
		res += 1
	if a < z and b < z and (c < x):
		res += 1
	if a < z and b < x and (c < y):
		res += 1
	return res

def helper(a, b, x, y, z):
	res = 0
	if a < x and a < y and (b < z):
		res += 1
	if a < x and a < z and (b < y):
		res += 1
	if a < y and a < z and (b < x):
		res += 1
	return res

def try2Comb(a, b, c, x, y, z):
	res = 0
	if a == b:
		res += helper(a, c, x, y, z)
	elif b == c:
		res += helper(b, a, x, y, z)
	else:
		res += helper(a, b, x, y, z)
	return res
t = int(input())
for _ in range(t):
	li = list(map(int, input().strip().split(' ')))
	(n, x, y, z) = li
	q = math.floor(math.sqrt(n))
	l = []
	for i in range(1, q + 1):
		if n % i == 0:
			if i == n / i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	l.sort()
	i = 0
	c = 0
	while i < len(l) and l[i] * l[i] * l[i] <= n:
		j = i
		k = len(l) - 1
		while k >= 0 and j <= k:
			if l[i] * l[j] * l[k] == n:
				if max(l[i], l[j], l[k]) <= max(x, y, z):
					if l[i] != l[j] != l[k]:
						c += tryComb(l[i], l[j], l[k], x, y, z)
					elif l[i] == l[j] == l[k]:
						c += 1
					elif l[i] == l[j] or l[j] == l[k] or l[i] == l[k]:
						c += try2Comb(l[i], l[j], l[k], x, y, z)
				j += 1
				k -= 1
			elif l[i] * l[j] * l[k] < n:
				j += 1
			else:
				k -= 1
		i += 1
	print(c)


import math
T = int(input())
for _ in range(T):
	(N, a, b, c) = map(int, input().split())
	div = []
	for i in range(1, int(math.sqrt(N)) + 1):
		if N % i == 0:
			if N / i == i:
				div.append(i)
			else:
				div.append(i)
				div.append(N / i)
	(f, s, t) = ([], [], [])
	for i in div:
		if i <= a:
			f.append(i)
		if i <= b:
			s.append(i)
		if i <= c:
			t.append(i)
	ans = 0
	for i in f:
		for j in s:
			if N % (i * j) == 0 and N / (i * j) <= c:
				ans += 1
	print(ans)


t = int(input())

def fac(n):
	s = set()
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	return sorted(list(s))
for I in range(t):
	(n, a, b, c) = [int(i) for i in input().split()]
	lis = fac(n)
	ans = 0
	for i in range(len(lis)):
		if lis[i] <= a:
			new_lis = fac(n // lis[i])
			new_num = n // lis[i]
			for j in range(len(new_lis)):
				if new_lis[j] <= b and new_num // new_lis[j] <= c:
					ans += 1
	print(ans)


def Factors(n):
	k = 0
	arr = []
	for i in range(1, int(n ** 0.5) + 2):
		if n % i == 0 and i not in arr:
			if i != int(n / i):
				arr.append(i)
				arr.append(int(n / i))
			else:
				arr.append(i)
	return arr
t = int(input())
for i4 in range(t):
	(n, a, b, c) = map(int, input().split())
	arr = Factors(n)
	count = 0
	for i in range(len(arr)):
		if n % arr[i] == 0 and arr[i] <= a:
			p = int(n / arr[i])
			for j in range(len(arr)):
				if p % arr[j] == 0 and arr[j] <= b:
					if int(p / arr[j]) <= c:
						count += 1
	print(count)


def factors(n):
	(l1, l2) = ([], [])
	for i in range(1, int(n ** 0.5) + 1):
		(q, r) = (n // i, n % i)
		if r == 0:
			l1.append(i)
			l2.append(q)
	if l1[-1] == l2[-1]:
		l1.pop()
	l2.reverse()
	return l1 + l2
for _ in range(int(input())):
	(n, a, b, c) = map(int, input().split())
	l = factors(n)
	ans = 0
	for i in l:
		if i <= a:
			p = n // i
			for j in l:
				if p % j == 0 and j <= b:
					if p // j <= c:
						ans += 1
	print(ans)


def fact(n):
	k = 0
	a = []
	for i in range(1, int(n ** (1 / 2)) + 2):
		if n % i == 0 and i not in a:
			if i != int(n / i):
				k += 2
				a.append(i)
				a.append(int(n / i))
			else:
				k += 1
				a.append(i)
	return a
t = int(input())
for i in range(t):
	k = 0
	(n, a, b, c) = [int(x) for x in input().split()]
	ar = fact(n)
	k = 0
	for i in ar:
		if n % i == 0 and i <= a:
			p = int(n / i)
			for j in ar:
				if p % j == 0 and j <= b:
					if int(p / j) <= c:
						k += 1
	print(k)


from time import time
startTime = time()

def isPrime(n):
	if n <= 11:
		return n in [2, 3, 5, 7, 11]
	(r, d) = (0, n - 1)
	while d % 2 == 0:
		r += 1
		d //= 2
	for a in [2, 3, 5, 7, 11]:
		(probablePrime, b0) = (False, pow(a, d, n))
		if b0 in [1, n - 1]:
			probablePrime = True
			continue
		bi = b0
		for i in range(1, r):
			bi = bi ** 2 % n
			if bi == 1:
				probablePrime = False
				break
			if bi == n - 1:
				probablePrime = True
				break
		if probablePrime == False:
			return False
	return True

def getPrimeFactors(n):
	if n % 2 == 0:
		primeFactors = [2]
		n //= 2
		while n % 2 == 0:
			primeFactors.append(2)
			n //= 2
	else:
		primeFactors = []
	factor = 3
	if isPrime(n):
		primeFactors.append(n)
		n = 1
	while n != 1:
		if n % factor == 0 and isPrime(factor):
			primeFactors.append(factor)
			n //= factor
			while n % factor == 0:
				primeFactors.append(factor)
				n //= factor
			if isPrime(n):
				primeFactors.append(n)
				n = 1
		factor += 2
	from itertools import groupby
	primeFactors = [[v, len(list(q))] for (v, q) in groupby(primeFactors)]
	return primeFactors

def iterate(factors, a, b, c):
	waysFound = 0
	(currentFactor, currentFactorAmount) = (factors[0][0], factors[0][1])
	for ai in range(0, currentFactorAmount + 1):
		if a * currentFactor ** ai > A:
			continue
		for bi in range(0, currentFactorAmount - ai + 1):
			ci = currentFactorAmount - ai - bi
			if b * currentFactor ** bi > B:
				continue
			if c * currentFactor ** ci > C:
				continue
			if len(factors) > 1:
				waysFound += iterate(factors[1:], a * currentFactor ** ai, b * currentFactor ** bi, c * currentFactor ** ci)
			else:
				waysFound += 1
	return waysFound
T = int(input())
for _ in range(T):
	(N, A, B, C) = [int(x) for x in input().split()]
	if N == 1:
		print(1)
		continue
	factors = getPrimeFactors(N)
	waysFound = iterate(factors, 1, 1, 1)
	print(waysFound)
import sys
print('Time taken =', time() - startTime, 'seconds', file=sys.stderr)
del sys


import sys
import math
from functools import reduce
from bisect import *
m = 1000000007

def find_ge(a, x):
	i = bisect_left(a, x)
	if i != len(a):
		return a[i]
	raise ValueError

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return a[i - 1]
	raise ValueError

def fact(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(pow(n, 0.5) + 1)) if n % i == 0)))
t = int(input())
for i in range(t):
	(n, p, q, r) = map(int, sys.stdin.readline().split(' '))
	l = [p, q, r]
	a = l[0]
	b = l[1]
	c = l[2]
	f = fact(n)
	ma = math.ceil(n / (b * c))
	setx = []
	count = 0
	for num in f:
		if num >= ma and num <= a:
			setx.append(num)
	for num in setx:
		d = n // num
		fd = sorted(fact(d))
		mb = math.ceil(d / c)
		i1 = fd.index(find_ge(fd, mb))
		i2 = fd.index(find_le(fd, b))
		count += i2 - i1 + 1
	print(count)


import math

def factors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n) + 1:
		if n % i == 0:
			if n / i == i:
				ans.append(int(i))
			else:
				ans.append(int(i))
				ans.append(int(n / i))
		i = i + 1
	return ans
t = int(input())
for _ in range(t):
	(n, a, b, c) = map(int, input().split())
	l_temp = [a, b, c]
	l_temp.sort()
	l1 = range(1, l_temp[0] + 1)
	l2 = range(1, l_temp[1] + 1)
	l3 = range(1, l_temp[2] + 1)
	lf = factors(n)
	l1r = [val for val in lf if val in l1]
	l2r = [val for val in lf if val in l2]
	l3r = [val for val in lf if val in l3]
	hasher = [0] * 1000000
	for ele in l3r:
		hasher[ele] = 1
	cnt = 0
	for e1 in l1r:
		for e2 in l2r:
			if n % (e1 * e2) == 0 and n // (e1 * e2) < l_temp[2] and (hasher[n // (e1 * e2)] == 1):
				cnt += 1
	print(cnt)


from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(pow(n, 0.5) + 1)) if n % i == 0)))
t = int(input())
for z in range(t):
	(n, a, b, c) = [int(x) for x in input().split()]
	factor = list(factors(n))
	factor.sort()
	ans = 0
	for i in factor:
		if i > a:
			break
		for j in factor:
			if j > b:
				break
			part = i * j
			if n % part == 0 and n // part <= c:
				ans += 1
	print(ans)