小圆是个很奇怪的女孩,所以她突然想知道有多少对整数$$$(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$$$,这不符合条件。