Бухгалтерия рассчитывает зарплату сотрудников за один рабочий день.

Для каждого сотрудника известны:

• имя name;
• базовая почасовая ставка r;
• время начала смены t1;
• время окончания смены t2.

Оплата считается по следующим правилам:

• первые 8 часов смены оплачиваются по ставке r;
• каждый час сверх 8, но не более чем до 12 часов включительно, оплачивается по ставке r * 3 / 2;
• каждый час сверх 12 оплачивается по ставке 2 * r.

Если при расчёте по ставке r * 3 / 2 получается нецелое число, дробная часть сохраняется до конца расчёта и отбрасывается только в самом конце.

Кроме того, для ночных часов действует надбавка 20% к уже определённой оплате этого часа. Час считается ночным, если он целиком относится к ночному интервалу с 22:00 до 06:00. Гарантируется, что смены начинаются и заканчиваются ровно в начале часа, поэтому каждый час смены однозначно является либо дневным, либо ночным.

Если t2 <= t1, это означает, что смена закончилась на следующие сутки в момент t2.

Длительность каждой смены — целое число часов от 1 до 16 включительно.

Для каждого сотрудника требуется определить итоговую сумму к выплате за смену. После всех вычислений результат округляется вниз до целого числа рублей.

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

Первая строка содержит целое число n — количество сотрудников.

Каждая из следующих n строк содержит описание одного сотрудника в формате name r t1 t2, где:

• name — непустая строка из латинских букв длиной не более 20;
• r — целое число, базовая ставка;
• t1, t2 — время начала и окончания смены в формате HH:00.

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

Для каждого сотрудника в отдельной строке выведите name pay, где pay — итоговая сумма к выплате в рублях после округления вниз.

Сотрудников нужно выводить в том же порядке, в котором они заданы во входных данных.

Ограничения

• 1 <= n <= 10^4
• 1 <= r <= 1000
• name состоит только из латинских букв
• длительность смены каждого сотрудника — от 1 до 16 часов включительно
• все моменты времени заданы в формате HH:00
• ввод осуществляется через стандартный ввод
• вывод осуществляется через стандартный вывод

Примеры

Пример 1

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

1
tKbsJarIZqHY 1 10:00 11:00

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

tKbsJarIZqHY 1

Пример 2

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

2
tKbsJarIZqHY 1 10:00 11:00
ZqHYpGXoFW 3 21:00 06:00

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

tKbsJarIZqHY 1
ZqHYpGXoFW 33