마법 시계

필트오버의 학자들이 매우 신비로운 마법 시계를 손에 넣었다. 이상한 바늘 움직임을 보고, 이 시계에 중요한 정보가 숨겨져 있을지도 모른다고 생각했다.

이 시계의 문자판에는 $60 \cdot 12 \cdot t$개의 눈금이 있으며, 시계 방향으로 $0$부터 $720t - 1$까지 번호가 매겨진다. 시계에는 분침과 시침이 있다. $\frac{1}{t}$분마다 (이 간격을 틱이라고 부른다) 분침은 12눈금, 시침은 1눈금을 움직인다. 일반 시계에서는 60분 동안 분침이 한 바퀴를 돌고, 시침은 $\frac{1}{12}$바퀴를 돈다.

이 시계에는 특이한 점이 있다. 어떤 틱에서 분침이 시침을 추월하거나 따라잡아야 하면, 분침은 시작 눈금으로 순간 이동한다. 분침이 $m$번 눈금을, 시침이 $h$번 눈금을 가리키고 두 바늘 사이의 거리가 $d = (h - m) \bmod (720t)$눈금이라고 하자. $0 < d < 12$이면 다음 틱 이후 분침은 0번 눈금에 있게 된다. 이때 시침은 평소처럼 계속 움직인다.

헤이머딩거는 이 시계의 본질과 성질에 관한 $q$개의 가설을 세웠다. $i$번째 가설을 검증하려면 바늘이 상태 $s_{i,1}$에서 상태 $s_{i,2}$로 가는 데 걸리는 시간을 알아내야 한다.

첫 줄에 공백으로 구분된 정수 $t$와 $q$가 주어진다 ($1 \le t \le 1500$, $1 \le q \le 10^6$). 이어지는 $q$개의 줄에는 각각 공백으로 구분된 정수 $h_1$, $m_1$, $h_2$, $m_2$가 주어진다. 이는 시작 상태와 끝 상태에서 시침과 분침이 가리키는 눈금 번호이다 ($0 \le h_{1,2}, m_{1,2} < 720t$).

각 질의의 답을 한 줄에 하나씩 출력한다. 답은 상태 $(h_1, m_1)$에서 $(h_2, m_2)$로 시계가 도달하는 데 필요한 최소 틱 수이다. 시작 상태에서 끝 상태에 도달하지 못하면 -1을 출력한다.