Двусторонние фильтры

Алексей только поступил в военную академию. На первом занятии по индивидуальным средствам защиты преподаватель рассказал историю из полевого госпиталя. В одной из операций санинструктору пришлось обслуживать отделение бойцов, используя плоские двусторонние фильтры для масок. Фильтры бывают трёх типов:

• Тип A – обе стороны стерильны.
• Тип B – одна сторона стерильна, другая уже загрязнена.
• Тип C – обе стороны загрязнены.

Чтобы экономить место, фильтры хранили строго одной стопкой на металлическом лотке. Каждый фильтр имеет две независимые стороны (верхнюю и нижнюю). Каждая сторона в любой момент бывает либо стерильной, либо загрязнённой. Лоток тоже считается поверхностью, которая бывает стерильной или загрязнённой (изначально лоток стерилен).

Правило контакта:

• Если загрязнённая сторона фильтра касается стерильной стороны другого фильтра, то стерильная сторона становится загрязнённой. Загрязнённая сторона при этом остаётся загрязнённой.
• Если загрязнённая сторона фильтра касается стерильного лотка, лоток становится загрязнённым.
• Если лоток уже загрязнён и к нему прижимают стерильную сторону фильтра, эта сторона становится загрязнённой. Лоток при этом остаётся загрязнённым.
• Если соприкасаются две загрязнённые стороны (или загрязнённая сторона и загрязнённый лоток) – ничего не меняется: обе поверхности остаются загрязнёнными.

Контакт есть между каждой парой соседних фильтров в стопке (нижняя сторона верхнего касается верхней стороны нижнего) и между нижним фильтром и лотком.

Перед каждым применением санинструктор берёт верхний фильтр из стопки и может использовать его, только если его верхняя сторона стерильна. После применения считается, что верхняя сторона использованного фильтра становится загрязнённой. Нижняя сторона этого фильтра не меняется сама по себе – она меняется только по правилам контакта. Между применениями санинструктор может полностью перестроить стопку как угодно: менять порядок фильтров, переворачивать любые фильтры любой стороной вверх, но после перестройки фильтры должны снова лежать одной стопкой на лотке. Сразу после каждой перестройки загрязнение распространяется по правилам контакта на все пары соприкасающихся поверхностей в новой стопке.

Для каждого запроса, зная количество фильтров типов A, B, C, определить максимальное число применений, которое можно выполнить до первой необходимости очистки, то есть до момента, когда невозможно сделать очередное применение (у верхнего фильтра верхняя сторона уже не стерильна).

Входные данные

В первой строке входного файла INPUT.TXT задано натуральное число Q (1 ≤ Q ≤ 10⁴). В каждой из следующих Q строк содержится по 3 натуральных числа A, B, C (1 ≤ A, B, C ≤ 10⁹).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на каждый запрос через пробел.

Пример

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]