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

Chef is a well known programmer. He owns a brand new Android phone of screen size of dimension n × m (n denotes the height of the phone and m denotes the width). Chef wants to design a program for painting the screen. He figured out c colors, which he will use to paint the screen. He wants to paint some rectangular section of pixels of the screen each with different color. Also Chef would like to use all of his c colors in painting.

Can you help Chef in finding number of different dimensions of rectangular section he can paint? In other words, find number of pairs x, y such that Chef can paint a rectangular section of dimension x × y (x denotes height, y denotes width) on the screen. Please note that Chef uses a fix orientation of his phone and is not allowed to rotate it, i.e. height always stays n and width always stays m and not the other way around.

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

First line of the input contains an integer T denoting the number of test cases. T test cases follow.
Only line of each test case contains three space separated integers n, m, c.

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

For each test case, output a single line containing the answer for the test case.

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

$1 ≤ T ≤ 100$
$1 ≤ n, m ≤ 10^{6}$
$1 ≤ c ≤ 10^{6}$

------ Subtasks ------ 

$Subtask #1: (40 points) 1 ≤ n, m ≤ 100, 1 ≤ c ≤ 10^{4}$
$Subtask #2: (60 points) original constraints$

----- Sample Input 1 ------ 
2
4 6 12
3 3 10
----- Sample Output 1 ------ 
3
0
----- explanation 1 ------ 
Test case 1. Possible pairs of dimensions are (2, 6), (3, 4) and (4, 3). Note that the rectangular section of dimension (1, 12) can't be painted as it can't fit into the screen, because 12 > 6.

Test case 2. There does not exist any rectangle of desired dimensions which can have 10 different pixels painted.

Difficulty: EASY
Tags: Number theory

Starter code:

Solutions:
import math
t = int(input())
for i in range(0, t):
	(n, m, c) = map(int, input().split(' '))
	r = math.floor(math.sqrt(c))
	p = 0
	for j in range(1, r + 1):
		if c % j != 0:
			continue
		d = c / j
		if j <= n and d <= m:
			p += 1
		if j != d and j <= m and (d <= n):
			p += 1
	print(p)


t = int(input())
for ni in range(t):
	(n, m, c) = map(int, input().split())
	if n > m:
		(n, m) = (m, n)
	count = 0
	for i in range(1, n + 1):
		if c % i == 0 and c // i <= m:
			count = count + 1
	print(count)


import math
for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	ans = 0
	for i in range(1, math.ceil(math.sqrt(c + 1))):
		if c % i == 0:
			b = c // i
			if i <= n and b <= m:
				ans += 1
			if i != b and i <= m and (b <= n):
				ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	if n > m:
		(n, m) = (m, n)
	ans = 0
	for i in range(1, n + 1):
		if c % i == 0 and c // i <= m:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	if c > n * m:
		print(0)
		continue
	A = []
	for i in range(1, c + 1):
		if c % i > 0:
			continue
		if c // i <= m and i <= n:
			A.append((i, c // i))
		elif c // i > m and i > n:
			break
	print(len(A))


for tc in range(int(input())):
	(n, m, c) = map(int, input().split())
	f = []
	cnt = 0
	for i in range(1, c + 1):
		if c % i == 0:
			f.append(i)
	for i in f:
		if i <= n and c // i <= m:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	l = []
	for i in range(1, c + 1):
		if c % i == 0:
			l.append([i, int(c / i)])
	k = []
	for i in range(len(l)):
		if l[i][0] <= n and l[i][1] <= m:
			k.append(l[i])
	print(len(k))


for _ in range(int(input())):
	(n, m, c) = [int(x) for x in input().split()]
	cnt = 0
	for i in range(1, c // 2 + 1):
		if c % i == 0:
			j = c // i
			if i <= n and j <= m:
				cnt += 1
	if c <= n:
		cnt += 1
	print(cnt)


t = int(input())
while t != 0:
	(w, h, c) = map(int, input().split())
	k = 0
	for j in range(1, c + 1):
		if c % j == 0:
			if j <= w:
				if c // j <= h:
					k += 1
			else:
				break
	print(k)
	t -= 1


t = int(input(''))
if 1 <= t <= 100:
	for _ in range(t):
		(n, m, c) = map(int, input().split())
		if 1 <= n <= 10 ** 6 and 1 <= m <= 10 ** 6 and (1 <= c <= 10 ** 6):
			x = 0
			if n > m:
				for i in range(1, m + 1):
					if c % i == 0 and i <= m and (c // i <= n):
						x += 1
			else:
				for i in range(1, n + 1):
					if c % i == 0 and i <= n and (c // i <= m):
						x += 1
			print(x)


for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	cnt = 0
	for i in range(1, n + 1):
		if c % i == 0:
			if c // i <= m:
				cnt += 1
	print(cnt)


T = int(input())
while T > 0:
	T = T - 1
	s = [int(i) for i in input().split()]
	x = s[0]
	y = s[1]
	c = s[2]
	pai = 0
	for i in range(1, x + 1):
		if c % i == 0 and c / i <= y:
			pai = pai + 1
	print(pai)


t = input()
for c in range(0, int(t)):
	(n, m, c) = input().split()
	n = int(n)
	m = int(m)
	c = int(c)
	count = 0
	if n > m:
		for x in range(1, m + 1):
			if c % x == 0:
				if n >= c // x:
					count = count + 1
	else:
		for y in range(1, n + 1):
			if c % y == 0:
				if m >= c // y:
					count = count + 1
	print(count)


num_cases = int(input())
for _ in range(num_cases):
	(n, m, c) = map(int, input().split())
	num_possible = 0
	for i in range(1, c + 1):
		if c % i == 0:
			(num_rows, num_cols) = (i, c // i)
			if num_rows <= n and num_cols <= m:
				num_possible += 1
	print(num_possible)


import math
for _ in range(int(input())):
	(n, m, c) = [int(num) for num in input().split(' ')]
	solutions = 0
	for h in range(1, c + 1):
		if c % h != 0:
			continue
		w = c / h
		if h <= n and w <= m:
			solutions += 1
	print(solutions)


import math
tests = int(input())
for i in range(tests):
	(n, m, c) = map(int, input().split())
	if n * m < c:
		print(0)
	else:
		count = 0
		end = math.floor(c ** 0.5) + 1
		for j in range(1, end):
			expected = c / j
			if expected == int(expected) and j <= n and (expected <= m):
				count += 1
			if expected == int(expected) and j != expected and (j <= m) and (expected <= n):
				count += 1
		print(count)


for i in range(int(input())):
	(n, m, c) = map(int, input().split())
	count = 0
	for i in range(1, n + 1):
		if c % i == 0:
			x = c // i
			if 1 <= x <= m:
				count += 1
	print(count)


for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	if n * m < c:
		print(0)
	else:
		count = 0
		p = min(n + 1, c // 2 + 1)
		for i in range(1, p):
			if c % i == 0:
				j = c / i
				if j <= m:
					count += 1
		if n >= c:
			count += 1
		print(count)


t = int(input())
for _ in range(t):
	(n, m, c) = map(int, input().split())
	ans = 0
	for x in range(1, n + 1):
		if c % x == 0:
			y = c / x
			if y <= m:
				ans += 1
	print(ans)


T = int(input())
for i in range(T):
	(n, m, c) = map(int, input().split())
	count = 0
	for a in range(1, n + 1):
		if c % a == 0 and c // a <= m:
			count += 1
	print(count)


for M in range(int(input())):
	(x, y, z) = map(int, input().split())
	cum = 0
	for i in range(1, x + 1):
		if z % i == 0 and z / i <= y:
			cum += 1
	print(cum)


for _ in range(int(input())):
	(l, w, c) = map(int, input().split())
	g = max(l, w)
	p = min(l, w)
	co = 0
	for i in range(1, p + 1):
		if c % i == 0:
			if c // i <= g:
				co += 1
	print(co)


t = int(input())
for i in range(t):
	ck = 0
	(n, m, c) = map(int, input().split())
	for i in range(1, n + 1):
		if c % i == 0:
			a = c / i
			if a <= m:
				ck += 1
	print(ck)


T = int(input())
for tc in range(T):
	(H, W, C) = map(int, input().split(' '))
	a = 0
	for i in range(1, H + 1):
		if C % i == 0 and C / i <= W:
			a = a + 1
	print(a)


import math

def fact(n, h, w):
	count = 0
	for i in range(1, h + 1):
		if n % i == 0:
			if n // i <= w:
				count += 1
	return count
for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	print(fact(c, m, n))


for _ in range(int(input())):
	(n, m, c) = map(int, input().rstrip().split())
	count = 0
	if n * m < c:
		pass
	else:
		for i in range(1, n + 1):
			if c % i == 0:
				if c // i <= m:
					count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, m, c) = map(int, input().split())
	count = 0
	x = min(n, m)
	y = max(n, m)
	for i in range(1, x + 1):
		if c % i == 0 and c // i <= y:
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	co = 0
	lst = list(map(int, input().split()))
	n = lst[0]
	m = lst[1]
	c = lst[2]
	for i in range(1, n + 1):
		if c % i == 0:
			if c / i <= m:
				co = co + 1
	print(co)


try:
	for _ in range(int(input())):
		(n, m, c) = map(int, input().split())
		cnt = 0
		for i in range(1, n + 1):
			if c % i == 0 and c / i <= m:
				cnt += 1
		print(cnt)
except EOFError:
	pass


t = int(input())
while t > 0:
	(n, m, c) = input().split(' ')
	n = int(n)
	m = int(m)
	c = int(c)
	count = 0
	for i in range(1, n + 1):
		if c % i == 0:
			if c // i <= m:
				count = count + 1
	print(count)
	t = t - 1


t = int(input())
for i in range(t):
	(a, b, d) = input().split()
	n = int(a)
	m = int(b)
	c = int(d)
	if n * m < c:
		print(0)
	else:
		count = 0
		for j in range(1, c + 1):
			if c % j == 0:
				if j <= n and c / j <= m:
					count += 1
		print(count)


import math
t = int(input())
for _ in range(t):
	s = 0
	(n, m, a) = map(int, input().split(' '))
	for i in range(1, min(n, m) + 1):
		if a % i == 0 and a / i <= max(n, m):
			s = s + 1
	print(s)


for _ in range(int(input())):
	(n, m, c) = list(map(int, input().split()))
	num = 0
	if c > m * n:
		print(num)
		continue
	if m < n:
		(mini, maxi) = (m, n)
	else:
		(mini, maxi) = (n, m)
	mini = c if c < mini else mini
	for i in range(1, mini + 1):
		if c // i <= maxi and c % i == 0:
			num += 1
	print(num)


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	coun = 0
	for j in range(1, a + 1):
		if c % j == 0 and c // j <= b:
			coun += 1
	print(coun)


t = int(input())
for i in range(t):
	l1 = list(map(int, input().strip().split(' ')))
	(n, m, c) = (l1[0], l1[1], l1[2])
	if n < m:
		sm = n
		bg = m
	else:
		sm = m
		bg = n
	ans = 0
	for d in range(1, sm + 1):
		s = c // d
		if d > c:
			break
		if s * d == c and bg >= s:
			ans = ans + 1
	print(ans)


T = int(input())
for _ in range(T):
	(H, W, C) = map(int, input().split())
	ans = 0
	for i in range(1, H + 1):
		if C % i == 0 and C / i <= W:
			ans += 1
	print(ans)


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(n, m, primeFactors, waysFound):
	(primeFactorValue, primeFactorAmount) = primeFactors[0]
	for i in range(0, primeFactorAmount + 1):
		new_n = n * primeFactorValue ** i
		new_m = m * primeFactorValue ** (primeFactorAmount - i)
		if new_n > N or new_m > M:
			continue
		if len(primeFactors) <= 1:
			waysFound += 1
		else:
			waysFound += iterate(new_n, new_m, primeFactors[1:], 0)
	return waysFound

def method1(N, M, C):
	if C == 1:
		return 1
	waysFound = iterate(1, 1, getPrimeFactors(C), 0)
	return waysFound

def method2(N, M, C):
	waysFound = 0
	for n in range(1, N + 1):
		if C % n != 0:
			continue
		m = C // n
		if m > M:
			continue
		waysFound += 1
	return waysFound
T = int(input())
for _ in range(T):
	(N, M, C) = [int(x) for x in input().split()]
	print(method1(N, M, C))


t = int(input())
while t > 0:
	(n, m, c) = map(int, input().split())
	divisors = [1]
	k = c
	for i in range(2, k + 1):
		if k % i == 0:
			divisors.append(i)
	k = len(divisors)
	i = 0
	pairs = []
	while i < k and divisors[i] <= n:
		j = 0
		while j < k and divisors[j] <= m:
			if divisors[i] * divisors[j] == c:
				pairs.append([divisors[i], divisors[j]])
			j += 1
		i += 1
	print(len(pairs))
	t -= 1


def variants(n, m, c):
	res = [(i, c // i) for i in range(1, c + 1) if c % i == 0 and i <= n and (c // i <= m)]
	return len(res)
for t in range(int(input())):
	(n, m, c) = input().split()
	(n, m, c) = (int(n), int(m), int(c))
	print(variants(n, m, c))


for t in range(int(input())):
	(n, m, c) = map(int, input().split())
	sq = int(c ** 0.5)
	cnt = 0
	for i in range(1, sq + 1):
		if c % i == 0:
			j = c / i
			if i <= n and j <= m:
				cnt += 1
			if i <= m and j <= n and (i != j):
				cnt += 1
	print(cnt)


import math
for _ in range(int(input())):
	(n, m, c) = map(int, input().split())
	out = 0
	for i in range(1, math.floor(math.sqrt(c)) + 1):
		if c % i == 0:
			(x, y) = (i, c / i)
			if x != y:
				if x <= m and y <= n:
					out += 1
				if x <= n and y <= m:
					out += 1
			elif x <= m and x <= n:
				out += 1
	print(out)


t = int(input())
for i in range(t):
	arr = [int(j) for j in input().split()]
	if arr[0] * arr[1] < arr[2]:
		count = 0
	else:
		count = 0
		if arr[0] <= arr[1]:
			first = arr[0]
			second = arr[1]
		else:
			first = arr[1]
			second = arr[0]
		for n in range(first, 0, -1):
			if arr[2] % n == 0:
				if arr[2] / n <= second:
					count = count + 1
				else:
					break
	print(count)


tc = int(input())
out = []
for i in range(tc):
	(n, m, c) = input().split()
	n = int(n)
	m = int(m)
	c = int(c)
	counter = 0
	for j in range(1, n + 1):
		if c % j == 0 and c / j <= m:
			counter += 1
	out.append(counter)
for i in out:
	print(i)


t = int(input())
for _ in range(0, t):
	y = input()
	n = int(y.split()[0])
	m = int(y.split()[1])
	c = int(y.split()[2])
	ans = 0
	for i in range(1, c + 1):
		if c % i == 0 and i <= n and (c / i <= m):
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(x, y, c) = map(int, input().split())
	m = 1
	sum = 0
	while m <= c:
		if c % m == 0:
			d = c / m
			if m <= x and d <= y:
				sum += 1
		m += 1
	print(sum)


import math

def get_ans(l, r, x, y, n):
	ctr = 0
	ex = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		x1 = i
		y1 = n // i
		if x1 * y1 == n and x1 <= x and (y1 <= y):
			ctr += 1
		if x1 * y1 == n and x1 <= y and (y1 <= x):
			ctr += 1
	if int(math.sqrt(n)) ** 2 == n:
		ex = 1
	if ctr == 0 and ex == 1:
		ctr += 1
	return ctr - ex
t = int(input())
while t:
	t -= 1
	count = 0
	(x, y, n) = map(int, input().split())
	count = get_ans(1, n, x, y, n)
	print(count)


def main():
	testCases = int(input())
	for i in range(testCases):
		(n, m, c) = map(int, input().split(' '))
		count = 0
		if n * m >= c:
			for i in range(1, n + 1):
				if c % i == 0 and int(c / i) <= m:
					count += 1
		print(count)
main()


def divisor(c):
	l = []
	for i in range(1, c + 1):
		if c % i == 0:
			l.append(i)
	return l
for _ in range(int(input())):
	(m, n, c) = map(int, input().split())
	l = divisor(c)
	count = 0
	if m * n < c:
		print(0)
	else:
		for i in l:
			for j in l:
				if i * j == c and i <= m and (j <= n):
					count += 1
		print(count)


for _ in range(int(input())):
	(n, m, c) = [int(x) for x in input().split()]
	x = 0
	a = min(n, m)
	m = m + n - a
	for i in range(1, a + 1):
		if c % i == 0 and c // i <= m:
			x += 1
	print(x)


for _ in range(int(input())):
	(n, m, c) = list(map(int, input().split()))
	if n * m < c:
		print(0)
		continue
	x = 0
	(n, m) = (min(n, m), max(n, m))
	for i in range(1, n + 1):
		if c % i == 0:
			if c // i <= m:
				x += 1
	print(x)


t = int(input())
for i in range(t):
	(a, b, c) = input().split(' ')
	a = int(a)
	b = int(b)
	c = int(c)
	k = 0
	for i in range(1, a + 1):
		if c % i == 0 and int(c / i) <= b:
			k += 1
	print(k)