아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Магические часы (Basic)

면접 대비

시간 제한2초메모리 제한1024 MB

요약
분침이 시침과 12칸 이내로 가까워지면 0번 칸으로 순간이동하는 시계에서, 목표 상태에 도달하는 최소 분을 구하거나 불가능하면 -1을 출력한다.
난이도

보통10점 중 7점

유형
그래프, BFS, 시뮬레이션, 수학
정답자
아직 제출이 없습니다

문제

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

Часы состоят из циферблата на 60⋅12=72060 \cdot 12 = 720 делений, пронумерованных от 00 до 719719 по часовой стрелке включительно, а также, собственно, из минутной и часовой стрелок. Каждую минуту минутная стрелка проходит 1212 делений, а часовая --- 11. Таким образом, на обычных часах с таким устройством за один час, то есть за 6060 минут, минутная стрелка проходит весь круг, а часовая --- 112\frac{1}{12}-ю круга.

Странность часов заключается в том, что когда на очередном тике минутная стрелка должна обогнать или догнать часовую, она телепортируется в начало. Таким образом, если минутная стрелка указывает на деление номер mm, а часовая --- на hh, и расстояние между ними равно d=(h−m) mod 720d = (h - m) \bmod 720 делений, то если 0<d<120 < d < 12, в конце следующей минуты минутная стрелка окажется на нулевом делении (тогда как часовая спокойно продолжит свой ход).

Хеймердингер выдвинул qq теорий относительно природы и способностей таких часов, и для проверки ii-й теории нужно научиться отвечать, через сколько времени стрелки из состояния s_i,1s\_{i, 1} перейдут в состояние s_i,2s\_{i, 2}.

입력

В первой строке ввода через пробел дано целое число qq --- количество запросов (1⩽q⩽20001 \leqslant q \leqslant 2000).

В ii-й из следующих qq строк дано описание ii-го запроса, состоящее из четырех целых чисел h_1h\_1, m_1m\_1, h_2h\_2 и m_2m\_2, разделенных пробелами --- номеров делений, на которые указывают часовая и минутная стрелка в начальном и конечном состояниях, соответственно (0⩽h_1,2,m_1,2<7200 \leqslant h\_{1,2}, m\_{1,2} < 720).

출력

Выведите qq строк --- ответы на все запросы, каждый в своей строке.

В качестве ответа на запрос выведите минимальное количество минут, спустя которое часы перейдут из состояния (h_1,m_1)(h\_1, m\_1) в состояние (h_2,m_2)(h\_2, m\_2), либо <<-1>> (без кавычек), если часы никогда не придут во второе состояния, находясь изначально в первом.

예제2

  1. 예제 1

    입력
    4
    0 0 1 12
    0 0 60 0
    11 0 12 0
    12 0 13 0
    
    예상 출력
    1
    60
    1
    -1
    
  2. 예제 2

    입력
    5
    133 0 415 0
    5 717 87 36
    193 0 230 0
    537 333 28 48
    459 76 2 0
    
    예상 출력
    1722
    82
    757
    -1
    -1