Мадока очень странная девочка, и поэтому ей внезапно стало интересно, сколько существует пар целых чисел \((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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество пар чисел, удовлетворяющих условию задачи.
Примечание
Для \(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\), что не подходит под условие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
2
3
4
5
100000000
|
1
4
7
10
11
266666666
|