---

# Задача 1
def task1():
    max_n = 0
    for n in range(1, 200):  # 200 взято с запасом
        bin_n = bin(n)[2:]  # двоичная запись числа N

        if n % 3 == 0:
            # дописываем три последние двоичные цифры
            tail = bin_n[-3:] if len(bin_n) >= 3 else bin_n.zfill(3)
            new_bin = bin_n + tail
        else:
            # остаток от деления умножаем на 3, переводим в двоичную и дописываем
            rem = (n % 3) * 3
            rem_bin = bin(rem)[2:]
            new_bin = bin_n + rem_bin

        R = int(new_bin, 2)  # переводим в десятичную систему

        if R < 76:
            max_n = n

    return max_n


# Задача 2
def to_ternary(n):
    """Переводит число n в троичную систему (строка)"""
    if n == 0:
        return "0"
    res = ""
    while n > 0:
        res = str(n % 3) + res
        n //= 3
    return res

def task2():
    min_R = 10**9  # большое число для поиска минимума
    for n in range(1, 500):  # 500 взято с запасом, чтобы наверняка
        tern = to_ternary(n)  # троичная запись N

        if n % 5 != 0:
            # меняем младший разряд на старший (в строке)
            if len(tern) > 1:
                tern_list = list(tern)
                tern_list[-1] = tern_list[0]
                tern_changed = "".join(tern_list)
            else:
                tern_changed = tern  # если число из одной цифры, замена ничего не меняет
            # остаток от деления на 5 в троичной системе
            rem = n % 5
            rem_tern = to_ternary(rem)
            new_tern = tern_changed + rem_tern
        else:
            # правая цифра дважды дублируется в конец
            new_tern = tern + tern[-1] * 2

        R = int(new_tern, 3)  # переводим троичную запись в десятичное число

        if R > 123 and R < min_R:
            min_R = R

    return min_R


# Задача 3
from functools import lru_cache

@lru_cache(maxsize=None)
def F(n):
    if n < 3:
        return 2
    if n % 2 == 0:  # чётное
        return F(n-1) + F(n-2) - n
    else:           # нечётное
        return F(n-2) - F(n-1) + 2*n

def task3():
    return F(30)


# Выводим ответы
print("Ответ 1:", task1())
print("Ответ 2:", task2())
print("Ответ 3:", task3())