В мире двоичных чисел решили разобраться, почему некоторые числа не дружат друг с другом, потому после ряда проведённых экспериментов было выявлено, что точно не дружат друг с другом те числа, которые нельзя поставить рядом так, чтобы в их последовательности не было двух и более единиц подряд, а также не было трёх и более нулей подряд.
Помогите понять жителям двоичного мира, сколько пар чисел от 1 до N нельзя точно никак подружить.
Например: есть два числа 4 и 5, в двоичной системе счисления они представлены как 100 и 101. Если их поставить как 101 и 100, получится 101100, что даёт две единицы подряд в строке, значит дружить они не будут, но если поставим наоборот 100 и 101 = 100101, то двух единиц подряд нет, а также нет трёх и более нулей подряд, значит числа могут подружиться.
Формат входных данных
На первой строке подаётся число N (1 <= N <= 10
5) – количество чисел в двоичном мире от 1 до N (включительно).
Формат выходных данных
Вывести на первой строке количество пар чисел, которые никак нельзя будет подружить друг с другом. Рассматриваются все числа от 1 до N, но все числа уникальны, потому не рассматриваются пары одинаковых чисел и повторяющиеся пары (если нельзя подружить число x с числом y, то пара (x, y) и (y, x) считается одной парой чисел).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
|
33
|