Анике приснился необычный сон. В нем она увидели бесконечную доску. На той доске бесконечно много строк и бесконечно много столбцов, содержащих бесконечно много чисел. Что интересно, каждое число появляется на доске конечное число раз.

Оказывается, доска соответствует вполне понятным рекурсивным правилам. Первая клетка каждой строки содержит номер этой строки (начиная с 1). Значение же в каждой последующей клетке равно сумме значения в предыдущей клетке и перевернутого значения в предыдущей клетке. Перевернутое число можно получить, если записать в обратном порядке цифры десятичного представления числа.

Формально, если A ( i , j ) - значение в i -й строке и j -м столбце доски, то:

1. A ( i , 1) = i

2. A ( i , j ) = A ( i , j - 1) + rev ( A ( i , j - 1)) , если j > 1 .

rev ( x ) - операция разворота числа в его десятичном представлении. Например, rev (345) = 543 , а rev (1040) = 0401 = 401 .

Затем во сне Аника увидела дружелюбного призрака Бозо, появившегося из-за угла. Он сказал ей: "Аника! Если ты правильно ответишь на мои вопросы, я подарю тебе коробку вкусного печенья. А вопросы мои будут такие: я буду давать тебе по два числа A и B , а ты должна будешь сказать, сколько на доске чисел, лежащих в диапазоне [ A : B ] ".

Аника, хоть она и во сне, очень хочет поесть печенья, поэтому просит вас помочь ответить на вопросы Бозо.

Витя безумно любит статистику. Ещё бы — у них со старшим братом день рождения приходится на один и тот же день года! Теперь каждый год в свой день рождения он записывает, сколько лет ему и его брату, и пытается найти в этих записях что-нибудь интересное.

Сегодня у Вити день рождения, и он показал свои записи Алёне. Витя знает, что она тоже любит исследовать всякие наборы чисел и находить в них закономерности. Алёна тут же заметила интересный момент: когда в один из прошлых дней рождения Вите было n лет, его брату было m лет, а сегодня Витя младше своего брата ровно в k раз!

Вернувшись вечером домой, Алёна заинтересовалась вопросом: а достаточно ли этих данных, чтобы вычислить, сколько лет исполнилось Вите сегодня? Алёна быстро справилась, а сможете ли вы решить эту сложную задачу и выяснить по числам n , m и k , сколько лет Вите?

Пятиклассник Лёня недавно прочитал статью о числах Фибоначчи.

Числами Фибоначчи называется числовая последовательность F ₁ , F ₂ , ..., F _n , ... , которая устроена следующим образом: F ₁ = 1 , F ₂ = 2 , а каждое следующие число вычисляется как сумма двух предыдущих: если i ≥ 3 , то F _i = F _{i - 1} + F _{i - 2} . Последовательность чисел Фибоначчи, таким образом, начинается с чисел 1, 2, 3, 5, 8, 13, 21, ... .

Сегодня Лёня изучает числа Фибоначчи с номерами от L до R , включительно. Так как Лёня очень любит число 3, ему стало интересно, сколько чисел Фибоначчи среди тех, которые он изучает сегодня, делятся на 3. Например, если L = 3 и R = 7 , то Лёня будет изучать числа F ₃ = 3 , F ₄ = 5 , F ₅ = 8 , F ₆ = 13 и F ₇ = 21 . Среди них на 3 делятся два числа: F ₃ = 3 и F ₇ = 21 .

Напишите программу, которая поможет Лёне найти ответ на волнующий его вопрос.

На Марсе используют систему счисления с основанием k . В отличие от привычной нам десятичной системы счисления, в этой системе счисления k цифр со значениями от 0 до k - 1 , а вес цифры в i -м разряде равен k ⁱ .

Например, пусть k = 8 . Запись 357 ₈ означает число 3·8 ² + 5·8 + 7 , в более привычной землянам десятичной системе счисления это число записывается как 239 ₁₀ . А число 192 ₁₀ , в системе счисления с основанием 8 записывается как 300 ₈ .

Ильдар — юный марсианин, и он очень любит круглые числа. Ильдар называет число достаточно круглым , если его запись в системе счисления с основанием k заканчивается хотя бы на n нулей. Сегодня Ильдар хочет найти i -е по порядку достаточно круглое число.

Помогите Ильдару, найдите i -е достаточно круглое в системе счисления с основанием k натуральное число и выведите его в десятичной системе счисления. Ильдар очень дружелюбен и гарантирует, что ответ в десятичной системе счисления не превосходит 10 ¹⁸ .

Арсений — молодой перспективный спортсмен. Всё, что любит делать Арсений — это тренироваться и вкусно есть. Также он отличается пунктуальностью. Только что он составил расписание из n пунктов: для каждого из следующих n часов он решил, что будет делать в это время — тренироваться или есть.

Арсений показал расписание своему тренеру, но ему оно не до конца понравилось. Тренер объяснил, что тренироваться в следующий час после приёма пищи вредно для здоровья.

Теперь Арсений хочет изменить свое расписание так, чтобы он ни разу не тренировался непосредственно после еды. При этом он хочет изменить минимальное число пунктов своего расписания. Помогите Арсению!