### 问题描述 小桥是一个非常奇怪的女孩。她总是喜欢思考一些奇怪的问题。今天，她想知道在 $1$ 到 $n$ 之间有多少对整数 $(a,b)$，满足它们的最小公倍数除以最大公约数不超过 $3$，也就是 $\dfrac{lcm(a,b)}{\gcd(a,b)} \leq 3$。 小桥对数学很感兴趣，她知道最大公约数是指两个整数的公共因子中最大的一个，最小公倍数是指两个整数的公共倍数中最小的一个。 你能帮助小桥解决这个问题吗？ ### 输入格式 输入包含多个测试用例。 第一行包含一个整数 $t$，表示测试用例的数量。 接下来 $t$ 行，每行一个整数 $n$ ，表示小桥要求解的范围。 ### 输出格式 对于每个测试用例，输出一个整数，表示满足条件的数对数量。 ### 样例输入 ```txt 6 1 2 3 4 5 100000000 ``` ### 样例输出 ```txt 1 4 7 10 11 266666666 ``` ### 样例说明 对于 $n=1$ 正好有一对数字 $(1, 1)$。 对于 $n=2$，只有 $4$ 对 $(1,1)、(1, 2)、(2,1)$ 和 $(2,2)$。 对于 $n = 3$，除 $(2,3)$ 和 $(3,2)$ 外，所有 $9$ 对都是合适的，因为它们的 $LCM$ 是 $6$，$GCD$ 是 $1$，这不符合条件。 ### 评测数据规模 对于 $100$% 的评测数据，$1\leq t \leq 10^4,1 \leq n \leq 10^8$。