Совунья, Лосяш и Пин устроили музыкальный эксперимент: их будильники начинают звонить одновременно в 8:00, а затем повторяются каждые $$$a$$$, $$$b$$$ и $$$c$$$ минут соответственно. Совунья уверяет, что иногда получается «аккорд», когда одновременно звучат хотя бы два устройства.

За первые $$$T$$$ минут (включительно) посчитайте, сколько раз Смешарики услышат такой «аккорд», т.е. сколько существует таких моментов $$$0 \le t \le T$$$, когда прозвонят хотя бы два будильника. Момент $$$t=0$$$ соответствует времени 8:00.

Тесты разделены на группы. В группе $$$1$$$ оценка потестовая ($$$25$$$ тестов по $$$2$$$ балла), баллы за группу $$$2$$$ начисляются только если пройдены все тесты данной группы.

Смешарики очень любят играть в настолки. За несколько лет у них накопилось много карточек от разных игр. Крош и Ёжик решили сравнить свои запасы. Для этого они придумали новую игру. В свой ход каждый должен выложить в ряд ровно на одну карточку больше, чем соперник. Первый ход делает Крош и выкладывает $$$1$$$ карточку, затем Ёжик $$$2$$$ карточки, Крош $$$3$$$ и так далее. Проигрывает тот, кто в свой ход не может выложить требуемое количество карточек.

Пин утверждает, что сможет без игры определить победителя. Ваша задача помочь ему в этом.

У Кроша есть $$$n$$$ карточек, у Ёжика — $$$m$$$. Нужно определить, кто выиграет и сколько карточек останется у каждого в момент окончания игры.

Тесты разделены на $$$2$$$ группы. В группе $$$1$$$ оценка потестовая (за каждый пройденный тест начисляется 2 балла). За вторую группу баллы начисляются, только если пройдены все тесты и первой, и второй группы.

Смешарики очень любят играть в пинг-понг. Однажды они решили устроить Большой Турнир Смешариков по круговой системе один на один. На турнир записалось целых $$$N$$$ игроков, каждому присвоен номер от $$$1$$$ до $$$N$$$. К сожалению, у Смешариков всего один стол, поэтому игры могут идти только последовательно. Пин отвечает за расписание матчей: он хочет составить такой список всех пар игроков (каждая пара встречается ровно один раз), чтобы в этом списке любые два соседних матча не имели общих игроков, так как играть две игры подряд очень утомительно. Крош с Нюшей уверяют, что это возможно при достаточно большом $$$N$$$, но Лосяш сомневается.

Помогите Пину составить верное расписание, если это возможно.

В задаче 50 тестов, каждый оценивается в 2 балла.

Тесты разделены на две группы. Вторая группа тестируется только в том случае, если все тесты первой группы пройдены.

Во время урока математики в Ромашковой долине Крош увлечённо изучал свойство векторов: $$$$$$ \overrightarrow{AB} + \overrightarrow{BC} = \overrightarrow{AC}. $$$$$$ Вдохновившись этой идеей сложения «по цепочке», он задумался: а можно ли придумать похожее правило для чисел с использованием наибольшего общего делителя?

Крош назвал тройку целых неотрицательных чисел $$$(A, B, C)$$$ НОД-свёртываемой, если выполняется равенство $$$$$$ \gcd(A + B,\; B + C) = A + C, $$$$$$ где $$$\gcd(x, y)$$$ — наибольший общий делитель неотрицательных целых чисел $$$x$$$ и $$$y$$$ (по соглашению, $$$\gcd(x, 0) = x$$$ при $$$x \ge 0$$$).

Пин, как истинный учёный, предложил проверить гипотезу на диапазонах значений: $$$$$$ L_A \le A \le R_A,\quad L_B \le B \le R_B,\quad L_C \le C \le R_C. $$$$$$

Помогите Смешарикам определить, сколько существует НОД-свёртываемых троек в заданных пределах.

В данной задаче $$$3$$$ группы тестов, не считая примеров. Обозначим $$$\max(R_A - L_A, R_B - L_B, R_C - L_C)$$$ за $$$D$$$.

Крош обнаружил в своем любимом компьютере новую игру. В игре есть $$$n$$$ злобных морковных монстров, стоящих в ряд и пронумерованных от 1 до $$$n$$$. В начале Крош может атаковать только первого монстра. Чтобы сразиться с монстром номер $$$i$$$ ($$$1 \lt i \le n$$$), необходимо сначала победить всех монстров с номерами меньше $$$i$$$.

У Кроша есть супероружие — Импульсный Луч с радиусом действия $$$k$$$. Если Крош атакует монстра с номером $$$m$$$, то урон распределяется так:

• монстр с номером $$$m$$$ получает $$$1$$$ единицу урона;
• монстр с номером $$$(m+1)$$$ — 2 единицы урона;
• монстр с номером $$$(m+2)$$$ — 3 единицы урона;
• и так далее...
• монстр с номером $$$(m+k-1)$$$ — $$$k$$$ урона (если он существует);

Другими словами, одним ударом Крош поражает подряд до $$$k$$$ монстров, при этом урон увеличивается на 1 с каждым последующим.

Монстры в этой игре также необычные. Если у монстра было $$$h_i \gt 0$$$ единиц здоровья, и он получил $$$d$$$ урона, то его новое здоровье станет равным $$$|h_i - d|$$$. Если здоровье становится равным нулю, монстр считается побежденным. Побежденные монстры больше не восстанавливаются, и их здоровье больше не изменяется, даже если последующие удары попадают по ним.

Если монстр, перед которым стоит Крош, побежден, он сразу перемещается к следующему живому монстру с наименьшим номером. Каждый удар Лучом можно наносить только по живому монстру, который стоит ближе всех к Крошу. При этом урон всё равно продолжают получать и побежденные монстры внутри радиуса действия Луча, если они попадают в соответствующие позиции — просто их здоровье остаётся равным нулю.

Игра завершается, когда Крош победит всех монстров. На каждый удар Лучом уходит ровно $$$1$$$ секунда.

У Кроша скоро встреча с Нюшей, и он хочет понять, успеет ли он пройти игру. Помогите Крошу посчитать минимальное количество секунд, которое потребуется для прохождения игры.

В данной задаче будет $$$5$$$ групп тестов. Баллы начисляются при прохождении всех тестов из группы.