A. Мадока и странные мысли
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мадока очень странная девочка, и поэтому ей внезапно стало интересно, сколько существует пар целых чисел $$$(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$$$).

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество пар чисел, удовлетворяющих условию задачи.

Пример
Входные данные
6
1
2
3
4
5
100000000
Выходные данные
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$$$, что не подходит под условие.