У класі діти сідають на стільці, розташовані по колу. Вони чогось чекають. З їхніх сяючих очей ми відчуваємо, що вони чекають чогось хорошого. Можливо, це не буде папір. Їх охоче розчавлюють, і багато хто вже слинять. Вони чекають на якусь їжу? За безлад? Або вони чекають найбільшого скарбу з усіх ласощів, самого шоколаду?
Так, учитель незабаром прийде до кімнати і принесе їм шоколад. На жаль, шоколад - це лише один 1, тому дітям доведеться ділитися шоколадом. Деякі можуть навіть не досягти успіху.
Допоможіть вчителю з’ясувати, скільки дітей можна їсти з шоколаду.
Завдання
Шоколадний стіл складається з \ (r \) рядків та \ (s \) стовпчиків шоколадних кубиків. Вчитель починає з того, що передає шоколад дитині по колу. Дитина відламує або один ряд, або одну колонку шоколаду, а решту передає дитині, яка сидить праворуч.
Хлопчики ненажерливі, і коли вони отримують шоколад, вони обриваються якомога більше. Отже, коли шоколад має більше рядків, ніж стовпців, вони розбивають один стовпець, інакше - один рядок.
Дівчата не такі жадібні, і вони також хочуть дотримуватися стрункої лінії. Тому вони відламують найменший можливий шматок, також один рядок або один стовпець, але вибирають те, що має менше кубиків шоколаду.
Дізнайтеся, скільки у дітей закінчився шоколад, якщо вчитель вибере, з якої дитини почати. Дитину підраховують лише один раз, навіть якщо він пропустив шоколад більше одного разу.
Формат введення
Перший рядок містить кількість класів \ (t \), в яких ця проблема повинна бути вирішена. На кожному з наступних рядків \ (t \) є опис одного класу, що складається з чисел \ (r \), \ (s \) та рядка \ (Z \) .
Шоколад має розміри \ (r \ раз s \) кубиків. \ (Z \) - рядок, що складається з літер «C» і «D», що описує, які діти хлопчики, а які дівчатка.
Букви "С" позначають хлопчиків і "Д" дівчаток, при цьому дитина сидить найближче до дошки в першій позиції струни \ (Z \), а дитина сидить праворуч від дитини у другій позиції, потім дитина, що сидить праворуч від іншого, тощо. Перша дитина в ланцюжку також сидить праворуч від останньої дитини.
Обмеження щодо розмірів вводу такі:
Кількість рядків і кількість стовпців кожного шоколаду становить принаймні \ (1 \) і не більше \ (10 ^ 6 \). У кожному класі є принаймні \ (1 \) учнів і щонайбільше \ (10 ^ 6 \) учнів.
Кількість класів становить максимум \ (10 ^ 6 \), а крім того, у всіх класах разом не більше \ (10 ^ 7 \) учнів. Усі цукерки разом мають не більше \ (10 ^ 7 \) рядків і не більше \ (10 ^ 7 \) стовпців.
У таблиці ви можете побачити верхні межі кількості класів \ (t \) та кількості учнів в одному класі \ (z \) та кількості рядків \ (r \) та стовпців \ (r \) один шоколад у кожному наборі входів.
| Максимум \ (t \) | \ (50 \) | \ (1 \, 000 \) | \ (10 ^ 6 \) | \ (10 \) | \ (10 ^ 6 \) |
| Максимум \ (z, r, s \) | \ (50 \) | \ (1 \, 000 \) | \ (20 \) | \ (10 ^ 6 \) | \ (10 ^ 6 \) |
Вихідний формат
Напишіть \ (t \) рядки для виходу, для кожного класу напишіть, скільки дітей може їсти шоколад, якщо вони поділять його так, як описано в завданні.
Приклад
Вхідні дані:
Вихід:
У третьому класі дівчата повинні їсти першими, адже хлопець з’їдає весь шоколад, який до нього потрапляє. У четвертому класі шоколад настільки великий, що його може з’їсти кожен. У п’ятому класі діти їстимуть у такому порядку: CCDDCDC. Таким чином, розміри шоколаду становитимуть (4.4), (4.3), (4.2), (3.2), (2.2), (2.1), (1.1), (0), 0) і всі їдять.
Тому що в школі мало грошей. ”
Завантаження
Для завантаження потрібно ввійти в систему
Запитання та обговорення
Наприкінці раунду у вас буде можливість обговорити рішення в дискусії під типовим рішенням.