← 返回题目列表

Codeforces · 1717/A

A. 小圆和奇怪的想法

中文机器翻译题面 查看原题

小圆是个很奇怪的女孩,所以她突然想知道有多少对整数$$$(a, b)$$$,其中$$$1 \leq a, b \leq n$$$,其中$$$\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3$$$。

在此问题中,$$$\operatorname{gcd}(a, b)$$$ 表示数字$$$a$$$ 和$$$b$$$ 的最大公约数,$$$\operatorname{lcm}(a, b)$$$ 表示数字$$$a$$$ 和$$$b$$$ 的最小公倍数。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含整数 $$$n$$$ ($$$1 \le n \le 10^8$$$)。

输出

对于每个测试用例,输出一个整数 - 满足条件的整数对的数量。

示例

输入 #1

6
1
2
3
4
5
100000000

输出 #1

1
4
7
10
11
266666666

注意

对于 $$$n = 1$$$ 来说,正好有一对数字 — $$$(1, 1)$$$ 并且它适合。

对于 $$$n = 2$$$,只有 $$$4$$$ 对 — $$$(1, 1)$$$、$$$(1, 2)$$$、$$$(2, 1)$$$、$$$(2, 2)$$$ 并且它们都适合。

对于 $$$n = 3$$$,所有 $$$9$$$ 对都是合适的,除了 $$$(2, 3)$$$ 和 $$$(3, 2)$$$,因为它们的 $$$\operatorname{lcm}$$$ 是 $$$6$$$,而 $$$\operatorname{gcd}$$$ 是 $$$1$$$,这不符合条件。