Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Gintoki has been very lazy recently and he hasn't made enough money to pay the rent this month. So the old landlady has given him a problem to solve instead, if he can solve this problem the rent will be waived. 
The problem is as follows:

A triplet of integers (A, B, C) is considered to be special if it satisfies the following properties for a given integer N :

A \bmod B = C
B \bmod C = 0
1 ≤ A, B, C ≤ N

Example: There are three special triplets for N = 3.
(1, 3, 1) is a special triplet, since (1 \bmod 3) = 1 and (3 \bmod 1) = 0. 
(1, 2, 1) is a special triplet, since (1 \bmod 2) = 1 and (2 \bmod 1) = 0.
(3, 2, 1) is a special triplet, since (3 \bmod 2) = 1 and (2 \bmod 1) = 0.

The landlady gives Gintoki an integer N. Now Gintoki needs to find the number of special triplets. Can you help him to find the answer?

------ Input Format ------ 

- 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 a single integer N. 

------ Output Format ------ 

- For each testcase, output in a single line the number of special triplets.

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

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{5}$

------ subtasks ------ 

Subtask #1 (5 points): $2 ≤N ≤10^{3}$

Subtask #2 (20 points): $2 ≤N ≤10^{4}$

Subtask #3 (75 points):  Original constraints

----- Sample Input 1 ------ 
3
3
4
5
----- Sample Output 1 ------ 
3
6
9
----- explanation 1 ------ 
Test case $1$: It is explained in the problem statement.

Test case $2$: The special triplets are $(1, 3, 1)$, $(1, 2, 1)$, $(3, 2, 1)$, $(1, 4, 1)$,  $(4, 3, 1)$, $(2, 4, 2)$. Hence the answer is $6$.

Test case $3$: The special triplets are $(1, 3, 1)$, $(1, 2, 1)$, $(3, 2, 1)$, $(1, 4, 1)$, $(4, 3, 1)$, $(1, 5, 1)$, $(5, 4, 1)$, $(5, 2, 1)$, $(2, 4, 2)$. Hence the answer is $9$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	for j in range(1, n // 2 + 1):
		for k in range(2 * j, n + 1, j):
			a = n // k
			b = n % k
			if b >= j:
				c += a + 1
			else:
				c += a
	print(c)


def soln(n: int) -> int:
	count = 0
	for c in range(1, n + 1):
		for b in range(c, n + 1, c):
			count += (n - c) // b
	return count
for _ in range(int(input())):
	n = int(input())
	print(soln(n))


for _ in range(int(input())):
	n = int(input())
	ans = 0
	for c in range(1, n // 2 + 1):
		for b in range(c, n + 1, c):
			ans += (n - c) // b
	print(ans)


for z in range(int(input())):
	n = int(input())
	c = 0
	c += n - 1
	i = 2
	while n >= 2 * i:
		c += n // i - 1
		i += 1
	for x in range(1, n):
		i = 2
		while n >= x * (i + 1):
			c += (n // x - 1) // i
			i += 1
	print(c)


import sys
for i in range(int(input())):
	n = int(sys.stdin.readline())
	ans = 0
	for c in range(1, n + 1):
		for b in range(2 * c, n + 1, c):
			ans += int(1 + (n - c) / b)
	print(ans)


for i in range(int(input())):
	n = int(input())
	ans = 0
	for c in range(1, n + 1):
		for b in range(c << 1, n + 1, c):
			ans += int(1 + (n - c) / b)
	print(ans)


import sys
from bisect import bisect_left as lb
from collections import deque
from queue import PriorityQueue as pq
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
for _ in range(ii()):
	n = ii()
	ans = 0
	for i in range(1, n + 1):
		for j in range(2 * i, n + 1, i):
			a = i
			d = j
			x = n
			y = (x - a) // d + 1
			ans += y
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	sum = 0
	for j in range(1, n):
		m = int(n / j)
		for k in range(1, m):
			sum = sum + int((m - 1) / k)
	print(sum)


n = 100000
pre = [0] * (n + 1)
for c in range(1, n // 2 + 1):
	for b in range(c, n + 1, c):
		if b % c == 0:
			for a in range(c, n + 1, b):
				if a % b == c:
					if a > b:
						pre[a] += 1
					else:
						pre[b] += 1
testcases = int(input())
for t in range(testcases):
	n = int(input())
	print(sum(pre[:n + 1]))


testCase = int(input())
while testCase:
	n = int(input())
	count = 0
	for i in range(1, n // 2 + 1):
		for j in range(2 * i, n + 1, i):
			a = n // j
			b = n % j
			if b >= i:
				count += a + 1
			else:
				count += a
	print(count)
	testCase = testCase - 1


for _ in range(int(input())):
	n = int(input())
	count = 0
	for c in range(1, n // 2 + 1):
		for b in range(2 * c, n + 1, c):
			x = n // b
			y = n % b
			if y >= c:
				count += x + 1
			else:
				count += x
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	k = 0
	for c in range(1, n + 1):
		for b in range(2 * c, n + 1, c):
			k += (n - c) // b + 1
	print(k)


n = 100000
computed_values = [0] * (n + 1)
for p in range(1, n // 2 + 1):
	for b in range(p, n + 1, p):
		if b % p == 0:
			for a in range(p, n + 1, b):
				if a % b == p:
					if a > p:
						computed_values[a] += 1
					else:
						computed_values[b] += 1
t = int(input())
for t in range(t):
	n = int(input())
	print(sum(computed_values[:n + 1]))


t = int(input())
for i in range(t):
	num = int(input())
	result = 0
	for i in range(1, num + 1):
		for j in range(i, num + 1, i):
			temp = (num - i) // j
			result += temp
	print(result)


for i in range(int(input())):
	number = int(input())
	cont = 0
	for c in range(1, number + 1):
		for b in range(2 * c, number + 1, c):
			increase = (number - c) // b + 1
			cont += increase
	print(cont)


num = int(input())
for i in range(num):
	a = int(input())
	b = 0
	for j in range(1, a + 1):
		for k in range(2 * j, a + 1, j):
			b = b + (a - j) // k + 1
	print(b)


for i in range(int(input())):
	n = int(input())
	c = 0
	for j in range(1, n + 1):
		for k in range(2 * j, n + 1, j):
			c += (n - j) // k + 1
	print(c)


for i in range(int(input())):
	numbers = int(input())
	count = 0
	for c in range(1, numbers + 1):
		for b in range(2 * c, numbers + 1, c):
			increase = (numbers - c) // b + 1
			count += increase
	print(count)


testcases = int(input())
for i in range(testcases):
	N = int(input())
	count = int(0)
	for C in range(1, N // 2 + 1):
		for B in range(2 * C, N + 1, C):
			count += 1 + (N - C) // B
	print(count)


testcases = int(input())
for testcase in range(testcases):
	n = int(input())
	count_ = 0
	for c in range(1, n // 2 + 1):
		for b in range(2 * c, n + 1, c):
			count_ += (n - c) // b + 1
	print(count_)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		for j in range(i, n + 1, i):
			temp = (n - i) // j
			ans += temp
	print(ans)


maxi = 10 ** 5 + 1
div = [[] for i in range(maxi + 1)]
for i in range(1, maxi):
	for j in range(2 * i, maxi, i):
		div[j].append(i)
t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	for b in range(2, n + 1):
		largest = n - n % b
		num_div = len(div[b])
		count += largest // b * num_div
		for j in range(0, num_div):
			if largest + div[b][j] <= n:
				count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	ans = 0
	for j in range(1, n // 2 + 1):
		c = j
		for k in range(2, n // c + 1):
			b = c * k
			y = (n - c) // b
			ans += y + 1
	print(ans)


t = int(input())
for x in range(t):
	n = int(input())
	s1 = 0
	for x in range(1, n):
		c = 2
		a = 1
		while 1 == 1:
			a = x * c
			if a > n:
				break
			s1 = s1 + (n - x) // a + 1
			c += 1
	print(s1)


M = 100001
l = [[] for i in range(M)]

def fact():
	for i in range(1, M):
		for j in range(2 * i, M, i):
			l[j].append(i)
fact()
t = int(input())
for test in range(t):
	n = int(input())
	s = 0
	for i in range(2, n + 1):
		x = n - n % i
		s += x // i * len(l[i])
		for j in range(len(l[i])):
			if l[i][j] + x <= n:
				s += 1
	print(s)


fact = []
for i in range(100001):
	fact.append([1])
for i in range(2, 100001):
	for j in range(i, 100001, i):
		fact[j].append(i)
	fact[i].remove(i)
for _ in range(int(input())):
	n = int(input())
	total = 0
	for i in range(2, n + 1):
		for j in fact[i]:
			x = (n - j) // i + 1
			total += x
	print(total)


MAX_N = 100000
totient = [1] * (MAX_N + 1)
dp = [0] * (MAX_N + 1)
for i in range(2, MAX_N + 1):
	for j in range(i, MAX_N + 1, i):
		totient[j] += 1
t = int(input())
for i in range(2, MAX_N + 1):
	for j in range(i, MAX_N + 1, i):
		dp[j] += totient[i - 1]
for i in range(2, MAX_N + 1):
	dp[i] += dp[i - 1]
while t > 0:
	n = int(input())
	print(dp[n])
	t = t - 1


fact = [[1] for i in range(100001)]
for i in range(2, 100001):
	for j in range(i, 100001, i):
		fact[j].append(i)
	fact[i].remove(i)
for _ in range(int(input())):
	n = int(input())
	print(sum([(n - j) // i + 1 for i in range(2, n + 1) for j in fact[i]]))


max_limit = 100000
answers = [0] * (max_limit + 1)
for c in range(1, max_limit // 2 + 1):
	for b in range(c, max_limit + 1, c):
		if b % c == 0:
			for a in range(c, max_limit + 1, b):
				if a % b == c:
					answers[a if a > b else b] += 1
no_testcases = int(input())
testcases = []
for i in range(no_testcases):
	val = int(input())
	testcases.append(val)
for val in testcases:
	print(sum(answers[0:val + 1]))


n = 100000
l = [0] * (n + 1)
for c in range(1, n + 1):
	for b in range(c, n + 1, c):
		if b % c == 0:
			for a in range(c, n + 1, b):
				if a % b == c:
					if a > b:
						l[a] += 1
					else:
						l[b] += 1
t = int(input())
for i in range(t):
	n = int(input())
	print(sum(l[:n + 1]))


upper_bound = 10 ** 5
aux_array = [0] * (upper_bound + 1)
for c in range(1, upper_bound // 2 + 1):
	for b in range(c, upper_bound + 1, c):
		if b % c == 0:
			for a in range(c, upper_bound + 1, b):
				if a % b == c:
					if a > b:
						aux_array[a] += 1
					else:
						aux_array[b] += 1
for _ in range(int(input())):
	n = int(input())
	print(sum(aux_array[:n + 1]))


for t in range(int(input())):
	N = int(input())
	counter = 0
	for c in range(1, N + 1):
		for b in range(c, N + 1, c):
			counter += (N - c) // b
	print(counter)


t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	for c in range(1, n // 2 + 1):
		for b in range(2 * c, n + 1, c):
			count += (n - c) // b + 1
	print(count)


limit = 100000
l = [0] * (limit + 1)
for i in range(1, limit // 2 + 1):
	for j in range(i, limit + 1, i):
		if j % i == 0:
			for k in range(i, limit + 1, j):
				if k % j == i:
					if k > j:
						l[k] += 1
					else:
						l[j] += 1
t = int(input())
for i in range(t):
	n = int(input())
	print(sum(l[:n + 1]))


n = 100000
compute = [0] * (n + 2)
for c in range(1, n // 2 + 1):
	for b in range(c, n + 2, c):
		if b % c == 0:
			for a in range(c, n + 2, b):
				if a % b == c:
					if a > b:
						compute[a] += 1
					else:
						compute[b] += 1
testcase = int(input())
for i in range(testcase):
	n = int(input())
	print(sum(compute[:n + 1]))


t = int(input())
while t:
	n = int(input())
	ans = 0
	for c in range(1, n + 1):
		for b in range(2 * c, n + 1, c):
			ans += int(1 + (n - c) / b)
	print(ans)
	t -= 1


n = 100000
p = [0] * (n + 1)
for c in range(1, n // 2 + 1):
	for b in range(c, n + 1, c):
		if b % c == 0:
			for a in range(c, n + 1, b):
				if a % b == c:
					if a > b:
						p[a] += 1
					else:
						p[b] += 1
for _ in range(int(input())):
	n = int(input())
	print(sum(p[:n + 1]))


N = 100000
pre_comp_values = [0] * (N + 1)
for C in range(1, N // 2 + 1):
	for B in range(C, N + 1, C):
		if B % C == 0:
			for A in range(C, N + 1, B):
				if A % B == C:
					if A > B:
						pre_comp_values[A] += 1
					else:
						pre_comp_values[B] += 1
testcase = int(input())
for t in range(testcase):
	N = int(input())
	print(sum(pre_comp_values[:N + 1]))


t = eval(input())
for i in range(0, t):
	n = eval(input())
	count = 0
	m = int(n / 2)
	for c in range(1, m + 1):
		for b in range(c * 2, n + 1, c):
			count += int((n - c) / b) + 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	for c in range(1, n + 1):
		for b in range(2 * c, n + 1, c):
			rem = n % b
			if rem < c:
				ans += n // b
			else:
				ans += n // b + 1
	print(ans)


n = 100000
dp = [0] * (n + 1)
for i in range(1, n + 1):
	for j in range(i, n + 1, i):
		if j % i == 0:
			for k in range(i, n + 1, j):
				if k % j == i:
					if k > j:
						dp[k] += 1
					else:
						dp[j] += 1
t = int(input())
for zz in range(t):
	m = int(input())
	print(sum(dp[:m + 1]))