Madoka is a very strange girl, and therefore she suddenly wondered how many pairs of integers $(a, b)$ exist, where $1 \leq a, b \leq n$, for which $\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3$.

In this problem, $\operatorname{gcd}(a, b)$ denotes the greatest common divisor of the numbers $a$ and $b$, and $\operatorname{lcm}(a, b)$ denotes the smallest common multiple of the numbers $a$ and $b$.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first and the only line of each test case contains the integer $n$ ($1 \le n \le 10^8$).


-----Output-----

For each test case output a single integer — the number of pairs of integers satisfying the condition.


-----Examples-----

Input
6
1
2
3
4
5
100000000
Output
1
4
7
10
11
266666666


-----Note-----

For $n = 1$ there is exactly one pair of numbers — $(1, 1)$ and it fits.

For $n = 2$, there are only $4$ pairs — $(1, 1)$, $(1, 2)$, $(2, 1)$, $(2, 2)$ and they all fit.

For $n = 3$, all $9$ pair are suitable, except $(2, 3)$ and $(3, 2)$, since their $\operatorname{lcm}$ is $6$, and $\operatorname{gcd}$ is $1$, which doesn't fit the condition.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
import sys
n = int(sys.stdin.readline())
for i in range(n):
	b = int(sys.stdin.readline())
	print(b + b // 2 * 2 + b // 3 * 2)


for s in [*open(0)][1:]:
	print((n := int(s)) + n // 2 * 2 + 2 * (n // 3))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	return n + 2 * (n // 2) + 2 * (n // 3)
for _ in range(int(input())):
	print(solve())


import sys
sys.setrecursionlimit(10 ** 6)
from collections import Counter, deque, defaultdict
import math
ip = sys.stdin.readline
op = sys.stdout.write
t = int(ip())
res = []
for _ in range(t):
	n = int(ip())
	count = n + n // 2 * 2 + n // 3 * 2
	res.append(count)
for val in res:
	op(str(val) + '\n')


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	k = n // 6
	m = n % 6
	ans = k * 16
	if m == 1:
		ans += 1
	elif m == 2:
		ans += 4
	elif m == 3:
		ans += 7
	elif m == 4:
		ans += 10
	elif m == 5:
		ans += 11
	print(ans)


for n in [*map(int, open(0))][1:]:
	print((n // 3 + n // 2) * 2 + n)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def Solve():
	for t in range(int(input())):
		n = int(input())
		print(n + (n // 3 + n // 2) * 2)
Solve()


import sys
input = sys.stdin.readline
read_int = lambda : int(input())
for _ in range(read_int()):
	n = read_int()
	print(n + ((n >> 1) + n // 3 << 1), flush=False)


for num in [*map(int, open(0))][1:]:
	print((num // 3 + num // 2) * 2 + num)


for x in [*map(int, open(0))][1:]:
	print((x // 3 + x // 2) * 2 + x)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	print(n + 2 * (n // 2 + n // 3))


import sys
N = int(input())

def rest(res):
	if res == 0:
		return 0
	if res == 1:
		return 1
	if res == 2:
		return 4
	if res == 3:
		return 7
	if res == 4:
		return 10
	if res == 5:
		return 11
for _ in range(N):
	n = int(sys.stdin.readline())
	(res, quo) = (n % 6, n // 6)
	print(quo * 16 + rest(res))


t = int(input())
import sys
for i in sys.stdin:
	n = int(i)
	print(n + n // 2 * 2 + n // 3 * 2)


def solve():
	n = int(input())
	b = 1
	print(n + 2 * (n // 2) + 2 * (n // 3))
t = int(input())
while t != 0:
	solve()
	t -= 1


trials = int(input())
answer_list = []
for x in range(trials):
	s = int(input())
	ans = 0
	mo = s % 6
	ans = s // 6 * 16
	if mo == 1:
		ans += 1
	if mo == 2:
		ans += 4
	if mo == 3:
		ans += 7
	if mo == 4:
		ans += 10
	if mo == 5:
		ans += 11
	answer_list.append(ans)
for g in answer_list:
	print(g)


def madoka():
	n = int(input())
	lst_ans = []
	for i in range(n):
		x = int(input())
		h = x // 3
		n = x % 3
		o = h % 2
		p = h // 2
		ans = p * 9 + p * 7 + h % 2 * 9 + 1
		if n == 0:
			if o == 0:
				ans = ans - 1
			else:
				ans = ans - 3
		if n == 1:
			ans = ans
		if n == 2:
			if o == 0:
				ans = ans + 3
			else:
				ans = ans + 1
		lst_ans.append(ans)
	for t in lst_ans:
		print(t)
madoka()


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	ans = n + 2 * int(n / 2) + 2 * int(n / 3)
	print(ans)
	t -= 1


import math
t = int(input())
L = []
for i in range(t):
	n = int(input())
	c = n + 2 * (n // 2 + n // 3)
	L.append(c)
for el in L:
	print(el)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	print(n + (n // 2 + n // 3) * 2)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


t = int(input())
so = []
for _ in range(t):
	n = int(input())
	sol = n
	sol += n // 3 * 2
	sol += n // 2 * 2
	so.append(sol)
for s in so:
	print(s)


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def str_list():
	s = input()
	return list(s[:len(s) - 1])

def instr():
	return input().strip()

def invr():
	return map(int, input().split())

def solve():
	n = int_num()
	ans = n + n // 2 * 2 + n // 3 * 2
	print(ans)

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


t = int(input())
l = []
for i in range(0, t):
	n = int(input())
	l.append(n)
for j in range(0, t):
	k = l[j] + l[j] // 2 * 2 + l[j] // 3 * 2
	print(k)


n = int(input())
l = []
for i in range(0, n):
	s = int(input())
	l.append(s)
for j in range(0, n):
	print(l[j] + l[j] // 2 * 2 + l[j] // 3 * 2)


def solve(n):
	max_3 = int(n / 3)
	max_2 = int(n / 2)
	max_1 = n
	return max_1 + max_2 * 2 + max_3 * 2
t = int(input())
res = []
for i in range(t):
	n = int(input())
	res.append(solve(n))
for i in res:
	print(i)


n = int(input())
arr = []
for i in range(n):
	m = int(input())
	if m % 6 == 1:
		a = (m - 1) * 8 // 3 + 1
		arr.append(a)
	elif m % 6 == 2:
		a = (m - 2) * 8 // 3 + 4
		arr.append(a)
	elif m % 6 == 3:
		a = (m - 3) * 8 // 3 + 7
		arr.append(a)
	elif m % 6 == 4:
		a = (m - 4) * 8 // 3 + 10
		arr.append(a)
	elif m % 6 == 5:
		a = (m - 5) * 8 // 3 + 11
		arr.append(a)
	else:
		a = m * 8 // 3
		arr.append(a)
for i in range(n):
	print(arr[i])


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
import math
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = inp()
	print(n + 2 * (n // 2) + 2 * (n // 3))


import sys
import math
from collections import Counter
from collections import defaultdict

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def solve(n):
	return n + n // 2 * 2 + n // 3 * 2
t = int(input())
for _ in range(t):
	n = get_ints()
	print(solve(n[0]))


for a in [*map(int, open(0))][1:]:
	print((a // 3 + a // 2) * 2 + a)


for _ in range(int(input())):
	x = int(input())
	print(x + 2 * (x // 2) + 2 * (x // 3))


for i in range(int(input())):
	n = int(input())
	print(2 * (n // 3) + 2 * (n // 2) + n)


m = int(input())
for j in range(0, m):
	n = int(input())
	print(2 * (n // 3) + 2 * (n // 2) + n)


t = int(input())
n = []
f = t
while t > 0:
	n.append(int(input()))
	t -= 1

def num(n):
	return n + 2 * (n // 2 + n // 3)
for i in range(f):
	print(num(n[i]))


import math
import sys
from collections import deque, OrderedDict, defaultdict
import heapq
from collections import Counter

def inp():
	return sys.stdin.readline().rstrip()

def mpp():
	return map(int, inp().split())

def lis():
	return list(mpp())

def yn(n):
	if n:
		return 'YES'
	else:
		return 'NO'

def fn(n):
	for i in range(n, 0, -1):
		if i % 3 == 0:
			return i * 2 + n
	return n

def main():
	t = int(input())
	for _ in range(t):
		n = int(inp())
		ans = n + n // 3 * 2 + n // 2 * 2
		print(ans)
main()


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	r = n + 2 * (n // 2 + n // 3)
	sys.stdout.write(str(r) + '\n')


for _ in range(int(input())):
	n = int(input())
	result = n
	result += n // 3 * 2
	result += n // 2 * 2
	print(result)


for t in range(int(input())):
	n = int(input())
	print(n + n // 2 * 2 + n // 3 * 2)


def count(n):
	a = n // 3 * 2
	if n % 2 == 0:
		return n * 2 + a
	else:
		return n * 2 + a - 1
t = int(input())
while t != 0:
	n = int(input())
	print(count(n))
	t -= 1


t = int(input())
while t != 0:
	n = int(input())
	if n % 2 != 0:
		print(n + (n - 1) + 2 * (n // 3))
	if n % 2 == 0:
		print(2 * n + 2 * (n // 3))
	t = t - 1


DEBUG = False

def answer(n):
	return n + 2 * (n // 2) + 2 * (n // 3)

def main():
	if DEBUG:
		import os
		os.chdir(os.path.dirname(__file__))
		global input
		f = open('Sample.txt')
		input = lambda : f.readline().strip()
	T = int(input())
	for t in range(T):
		n = int(input())
		print(answer(n))
main()


t = int(input())
for i in range(t):
	n = int(input())
	ans = n + (n // 2 + n // 3) * 2
	print(ans)


for h in range(int(input())):
	n = int(input())
	print(n + 2 * (n // 3 + n // 2))


test = int(input())
for t in range(test):
	n = int(input())
	p = n + 2 * (n // 2) + 2 * (n // 3)
	print(p)


case = int(input())
for _ in range(case):
	res = int(input())
	x = res + res // 2 * 2
	c = res // 3 * 2
	print(x + c)


for _ in range(int(input())):
	n = int(input())
	w = n // 3
	x = n // 2
	print(n + 4 * w + 2 * (x - w))


for _ in range(int(input())):
	n = int(input())
	ans = n + 2 * (n // 2) + 2 * (n // 3)
	print(ans)


from math import factorial as fact, comb as ncr
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as cnt
lin = lambda : list(map(int, input().split()))
nin = lambda : int(input())
sin = lambda : str(input())
bi = lambda n: bin(n).replace('0b', '')
yes = lambda : print('YES')
no = lambda : print('NO')
for pratyush in range(int(input())):
	n = nin()
	print(n + n // 2 * 2 + n // 3 * 2)


t = int(input())
while t:
	n = int(input())
	print(n + n // 2 * 2 + n // 3 * 2)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	ans = n + n // 3 * 2
	if n % 2 == 1:
		ans = ans + n - 1
	else:
		ans = ans + n
	print(ans)


for tc in range(int(input())):
	n = int(input())
	out = n
	if n == 1:
		print(1)
	elif n == 2:
		print(4)
	else:
		if n % 2 == 0:
			out += n
		else:
			out += n - 1
		if n % 3 == 0:
			out += 2 * (n / 3)
		else:
			out += 2 * ((n - n % 3) / 3)
		print(int(out))


def findNum(n):
	return n + 2 * (n // 2) + 2 * (n // 3)
counter = int(input())
for i in range(counter):
	n = int(input())
	print(findNum(n))


for _ in range(int(input())):
	n = int(input())
	d2 = d3 = db = ans = 0
	if n > 3:
		ans = 7
	elif n == 1:
		print(1)
		continue
	elif n == 2:
		print(4)
		continue
	elif n == 3:
		print(7)
		continue
	db = n // 6
	d2 = n // 2
	d3 = n // 3
	d2 -= db
	d3 -= db
	d2 -= 1
	d3 -= 1
	ans += db * 4 + d2 * 2 + d3 * 2 + n - 3
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	print(2 * math.floor(n / 2) + 2 * math.floor(n / 3) + n)


import math as m

def ss(n):
	c = 0
	c += n // 3
	c += n // 2
	if c == 0:
		return n
	return 2 * c + n
for _ in range(int(input())):
	n = int(input())
	print(ss(n))


import math
for i in range(int(input())):
	s = int(input())
	print(s + s // 2 * 2 + s // 3 * 2)


t = int(input())
for i in range(t):
	n = int(input())
	nn = int(n / 2)
	nnn = int(n / 3)
	print(n + nn * 2 + nnn * 2)


def calc(n):
	z = n
	z += n // 2 * 2
	z += n // 3 * 2
	return z
t = int(input())
for _ in range(t):
	n = int(input())
	print(calc(n))


t = int(input())
for _ in range(t):
	n = int(input())
	cnt_div_2 = n // 2
	cnt_dib_3 = n // 3
	print(n + cnt_dib_3 * 2 + cnt_div_2 * 2)


t = int(input())
for i in range(0, t):
	n = int(input())
	print(n + 2 * (n // 2) + 2 * (n // 3))


def cal(n):
	ans = n
	ans += 2 * (n // 3)
	ans += 2 * (n // 2)
	return ans
for jj in range(int(input())):
	n = int(input())
	print(cal(n))


t = int(input())
for t1 in range(t):
	n = int(input())
	ans = 0
	ans += 3 * (n // 2) + 3 * (n // 3) + (n - n // 2 - n // 3)
	print(ans)


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def valid(i, j, n, m):
	if i < n and i >= 0 and (j >= 0) and (j < m):
		return True
	return False

def sumn(i, n):
	return (n - i) * (i + n) // 2

def sqfun(a, b, c):
	return (-b + math.sqrt(b * b - 4 * a * c)) / 2 * a

def value():
	return tuple(map(int, input().split()))

def values():
	return tuple(map(int, sys.stdin.readline().split()))

def inlst():
	return [int(i) for i in input().split()]

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(input())

def inps():
	return int(sys.stdin.readline())

def instr():
	return input()

def stlst():
	return [i for i in input().split()]

def solve():
	n = inp()
	return n + 2 * (n // 2) + 2 * (n // 3)
for i in range(inp()):
	print(solve())


inp1 = int(input())
for t in range(inp1):
	n = int(input())
	cnt = 0
	print(n + 2 * (n // 2) + 2 * (n // 3))


t = int(input())
for i in range(t):
	n = int(input())
	x = n + 2 * (n // 2) + 2 * (n // 3)
	print(x)


t = int(input())
for i in range(t):
	n = int(input())
	print(n // 1 + n // 2 * 2 + n // 3 * 2)