Given an integer N, find the number of tuples (w, x, y, z) such that 1 ≤ w, x, y, z ≤ N and \frac{w}{x} + \frac{y}{z} is an integer.

For example, if N = 2, the tuple (1,2,1,2) satisfies both conditions, i.e. \frac{1}{2} + \frac{1}{2} = 1 is an integer, however (1,1,1,2) does not since \frac{1}{1} + \frac{1}{2} = 1.5 is not an integer.

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

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input containing one integer, N.

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

- For each test case, print a new line containing a single integer, the answer to that test case.

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

$1 ≤ T ≤ 150$
$1 ≤ N ≤ 1000$
- The sum of $N$ over all test cases does not exceed $10^{4}$

----- Sample Input 1 ------ 
3
2
3
7
----- Sample Output 1 ------ 
10
31
355

----- explanation 1 ------ 

Test Case $1$: There are $2^{4} = 16$ tuples to consider, out of them the only ones that are invalid are those where one of the fractions is $\frac{1}{2}$ and the other is an integer.
The valid tuples are $\{(1, 1, 1, 1), (1, 1, 2, 1), (1, 1, 2, 2), (1, 2, 1, 2), (2, 1, 1, 1), (2, 1, 2, 1), (2, 1, 2, 2), (2, 2, 1, 1), (2, 2, 2, 1), (2, 2, 2, 2)\}$.

Test Cases $2$ and $3$: There are too many tuples to list them in these cases. However, you may verify that among the $3^{4} = 81$ and $7^{4} = 4901$ tuples respectively only $31$ and $355$ of them satisfy the conditions in the problem statement.

Difficulty: VERY_HARD
Tags: Number theory

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
from collections import defaultdict
from math import gcd
from functools import lru_cache
t = int(input())

@lru_cache(None)
def rf(x, y):
	g = gcd(x, y)
	y = y // g
	x = x // g
	x -= y * (x // y)
	return (x, y)

def solve(N):
	nums = [x for x in range(1, N + 1)]
	ans = 0
	d = defaultdict(int)
	for x in nums:
		for y in nums:
			(sx, sy) = rf(x, y)
			d[sx, sy] += 1
	for (k, v) in d.items():
		(sx, sy) = k
		if sx > 0:
			nsx = sy - sx
		else:
			nsx = sx
		ans += d[nsx, sy] * d[sx, sy]
	print(ans)
while t:
	N = int(input())
	solve(N)
	t -= 1


table = [1, 9, 21, 48, 53, 130, 93, 195, 205, 302, 191, 538, 243, 500, 619, 694, 365, 1003, 429, 1190, 1023, 980, 567, 1886, 1007, 1226, 1391, 1964, 787, 2804, 859, 2179, 1943, 1794, 2235, 3780, 1097, 2094, 2437, 4090, 1273, 4520, 1357, 3680, 4325, 2726, 1541, 5980, 2621, 4497, 3535, 4620, 1815, 6082, 4217, 6592, 4117, 3712, 2105, 10026, 2179, 4036, 6899, 6510, 5271, 8394, 2473, 6648, 5331, 9632, 2693, 12307, 2761, 5092, 8681, 7684, 6785, 10522, 3099, 12672, 7821, 5856, 3323, 15920, 7557, 6236, 7219, 12140, 3633, 17830, 8473, 9916, 7837, 7040, 8793, 17782, 4047, 11345, 12795, 16024, 4281, 14942, 4405, 15114, 18329, 8208, 4655, 21312, 4729, 17610, 9873, 20094, 4963, 17238, 11295, 13394, 15971, 9476, 12129, 31946, 8967, 9812, 11323, 14598, 12149, 28318, 5775, 18425, 12023, 21936, 6059, 29122, 13973, 11102, 24435, 21550, 6395, 22134, 6533, 33240, 13551, 11990, 15659, 37002, 15239, 12340, 21547, 18280, 7151, 35264, 7251, 24826, 22627, 27988, 16633, 36318, 7557, 13764, 15843, 36884, 18007, 31891, 7981, 20880, 33343, 14650, 8343, 50182, 13891, 31092, 26129, 22174, 8659, 29790, 28997, 36696, 18145, 16024, 9135, 60558, 9107, 34722, 18789, 31720, 20763, 32374, 22243, 24970, 38587, 36042, 9867, 50054, 9919, 17832, 41479, 39270, 10245, 51278, 10347, 50435, 21165, 18724, 24283, 51150, 23735, 19300, 33541, 45498, 25759, 72418, 11079, 28956, 22899, 20258, 25321, 66656, 26277, 20678, 23649, 60170, 27653, 40552, 12021, 58010, 53257, 21572, 12315, 58896, 12367, 45808, 52513, 42694, 12699, 63672, 28409, 33290, 26253, 49278, 13227, 94082, 13125, 37023, 38915, 34472, 44785, 46098, 31885, 46470, 27999, 49402, 14081, 94978, 32881, 25092, 58423, 50184, 14379, 48986, 32921, 74564, 44957, 26114, 14943, 90636, 32933, 56630, 30535, 38938, 15337, 95728, 15377, 64104, 65023, 27570, 52623, 75126, 15709, 28202, 48847, 103010, 16051, 54796, 16235, 41992, 67349, 63008, 37749, 105317, 27863, 61332, 33827, 43186, 17037, 85406, 37897, 57914, 69711, 30734, 40995, 118116, 39855, 31170, 35719, 73956, 39275, 89574, 18009, 94442, 36603, 66898, 18393, 112242, 18341, 32708, 108691, 47840, 18809, 63736, 44281, 102478, 38447, 72072, 45305, 106916, 65003, 34268, 39293, 65978, 44919, 129876, 19725, 51002, 60977, 35580, 44381, 146900, 20119, 56893, 41129, 104766, 47987, 103002, 45963, 69940, 85819, 36934, 21203, 100562, 21257, 113792, 86471, 104618, 21465, 72858, 47695, 55670, 91799, 38812, 22245, 185232, 36975, 39002, 69535, 116506, 49073, 75648, 22539, 93954, 69421, 83336, 52167, 109120, 22975, 88704, 92475, 78444, 54847, 149846, 23473, 120870, 47389, 41866, 24033, 135590, 107737, 42264, 73701, 61800, 24487, 160592, 57805, 121555, 49425, 43552, 54629, 170270, 24807, 44114, 105245, 147646, 25157, 85084, 59377, 65032, 122053, 96596, 60001, 157410, 25693, 94642, 52217, 66684, 59831, 131180, 58101, 129392, 53295, 102118, 26945, 238158, 26543, 47138, 82379, 90714, 91465, 91578, 61823, 70040, 117607, 100748, 27853, 194028, 27657, 104860, 114543, 71318, 66663, 94804, 28475, 184504, 128097, 109760, 28663, 135950, 63159, 50838, 58287, 160018, 29235, 204825, 68217, 74484, 58897, 52052, 133101, 180946, 29579, 52498, 121433, 153212, 30157, 202414, 30213, 125630, 124413, 53492, 30791, 210178, 69515, 112368, 61651, 103876, 72575, 104708, 105827, 164232, 95873, 55532, 31935, 263364, 73931, 55658, 134151, 125018, 70121, 151936, 32125, 107914, 64787, 174082, 32701, 154330, 77275, 126384, 194747, 136580, 75061, 111206, 33253, 164814, 67051, 59038, 34005, 288304, 73557, 129370, 106413, 86202, 34209, 224748, 77207, 132461, 139233, 60408, 75877, 163528, 81211, 130744, 70025, 227820, 35035, 174704, 35221, 89832, 210331, 62402, 84209, 262588, 60283, 130146, 109303, 188106, 84459, 121152, 79525, 121440, 73143, 64350, 126975, 313790, 36445, 64576, 73723, 181296, 81187, 249834, 37127, 94700, 113579, 203458, 89239, 229426, 85421, 66192, 155051, 96606, 38315, 189986, 89823, 297648, 164393, 67230, 38717, 182784, 84663, 68256, 190591, 130656, 39387, 258390, 39293, 209248, 78999, 148594, 134491, 287116, 39409, 111853, 79765, 204024, 91151, 134408, 94283, 134724, 240269, 71106, 41025, 281014, 96581, 149048, 82073, 169790, 41421, 267022, 187007, 105124, 82887, 160592, 42159, 357076, 41579, 157094, 127375, 106622, 142237, 141310, 42529, 208586, 179187, 154758, 100715, 294388, 42701, 75470, 176145, 287058, 43155, 144842, 43587, 222008, 177565, 76678, 99689, 323994, 119043, 76984, 189069, 112014, 104817, 411148, 44165, 148504, 88603, 78400, 98209, 211798, 155915, 173212, 137463, 274850, 45291, 151844, 45705, 238640, 187021, 177422, 46291, 324021, 107699, 250918, 193663, 116858, 46389, 155246, 102131, 192948, 141889, 176038, 47399, 423506, 46739, 82518, 203491, 158142, 215001, 235906, 113501, 121276, 95699, 174380, 112227, 409024, 47891, 84366, 277131, 189908, 48591, 162102, 110235, 318104, 97465, 187856, 49459, 337550, 107361, 180724, 98585, 204204, 116669, 327316, 49657, 126208, 302829, 87788, 110075, 305596, 118931, 88476, 101137, 372274, 50821, 329676, 120331, 285558, 208017, 89104, 115885, 241392, 51289, 186894, 156667, 172282, 123471, 349992, 238501, 131940, 104321, 91920, 53103, 530384, 118359, 147407, 104537, 133076, 178767, 268062, 53231, 353634, 179777, 192570, 126327, 250962, 53385, 94086, 320627, 264044, 125771, 267510, 54185, 275642, 233379, 203598, 54821, 331598, 119317, 95674, 166753, 292928, 125001, 351972, 55177, 228486, 110707, 213984, 121751, 486496, 55351, 97520, 239995, 365790, 55913, 186700, 127133, 142626, 335479, 99074, 133685, 356582, 56799, 408868, 113311, 143786, 57443, 283744, 194365, 191194, 241379, 101172, 137685, 521924, 135171, 224834, 236333, 350612, 126603, 193872, 58279, 148058, 117375, 213326, 133469, 512214, 137715, 103144, 241631, 149780, 59813, 401070, 141651, 411093, 180881, 104256, 139737, 281714, 272107, 232152, 120543, 200868, 60999, 461618, 60709, 318000, 121069, 233796, 133445, 452064, 145041, 107000, 373065, 312564, 61441, 204914, 61979, 206044, 374837, 232768, 62603, 427680, 62283, 226282, 124425, 352268, 220011, 209100, 137843, 336170, 256469, 110798, 64087, 711690, 106845, 110306, 126367, 160382, 216201, 316212, 221761, 263942, 127717, 350726, 153469, 302810, 64649, 241706, 385695, 215720, 65161, 445224, 65349, 331756, 274199, 114464, 66177, 537234, 142937, 114596, 207509, 344804, 154513, 434838, 155073, 220056, 200601, 258328, 292993, 312776, 66615, 117380, 134115, 528676, 67443, 484589, 67237, 360432, 275019, 117912, 68277, 411510, 153221, 246062, 339371, 171994, 162993, 227878, 150389, 426530, 296943, 120374, 165077, 662328, 163435, 264664, 289917, 229582, 150839, 230580, 69747, 176400, 211597, 504024, 70443, 518606, 163797, 122524, 286487, 177770, 160007, 460398, 71131, 462484, 140891, 124190, 167821, 655788, 241037, 124486, 216421, 351226, 72005, 471684, 251403, 181232, 143529, 126582, 333213, 630886, 72081, 270976, 144209, 369574, 72995, 242028, 174775, 301788, 555293, 280840, 73773, 344552, 172163, 403442, 147031, 494302, 74109, 366436, 161775, 187670, 319999, 130728, 169255, 709276, 126053, 287926, 226845, 188586, 163639, 507594, 75443, 379595, 326461, 273184, 76183, 494474, 171375, 132582, 461815, 313032, 76433, 253236, 179121, 565772, 231461, 133980, 77677, 466466, 167877, 299406, 324177, 414060, 185429, 728296, 77351, 381208, 154025, 291028, 170109, 365622, 78021, 136928, 318677, 496444]
T = int(input())
while T:
	T -= 1
	N = int(input())
	ans = 0
	for i in range(N):
		ans += table[i]
	print(ans)