쉬운 최단경로 문제

농부 John의 목장은 특이하게 생겼다. 볼록 다각형을 이루는 N개의 말뚝이 있고, 말뚝 쌍마다 두 말뚝을 선분으로 잇는 밧줄이 있다. 밧줄은 높아서 소들이 넘어 다니기 어렵다. Alice와 Bessie는 가장 친한 친구지만, 농부 John이 둘을 떼어 놓아서 지금은 멀리 떨어져 있다. 위 그림은 N=4일 때의 한 예이다. 밧줄은 총 6개다. Alice는 Bessie가 있는 곳에 놀러 가려고 한다. 밧줄을 넘기는 쉽지 않으므로, 넘는 밧줄의 개수를 최소로 하려고 한다. 위 그림의 경우 밧줄을 2번 넘는 것이 최적이다. 농부 John이 두 소의 위치를 자주 바꾸므로, Q개의 위치 쌍마다 넘어야 하는 밧줄의 최소 개수를 구한다. Alice와 Bessie가 문제를 풀 수 있게 도와주자. 두 개 이상의 밧줄이 교차하는 점을 통해 넘는 것은 한꺼번에 넘은 것으로 인정하지 않는다. 예를 들어 3개의 밧줄이 교차하는 점을 통해 한꺼번에 넘으면 3번으로 센다. 같은 밧줄을 여러 번 넘으면 그때마다 센다.

첫 번째 줄에 말뚝의 수 N (3 ≤ N ≤ 5,000)이 주어진다. 두 번째 줄부터 N개의 줄에 정수 x와 y가 주어지며, 이는 말뚝의 좌표이다. 말뚝은 반시계 방향 순서로 주어진다. N+2번째 줄에 쿼리의 개수 Q (1 ≤ Q ≤ 10,000)가 주어진다. N+3번째 줄부터 Q개의 줄에 정수 x1, y1, x2, y2가 주어진다. (x1, y1)은 Alice의 좌표이고, (x2, y2)는 Bessie의 좌표이다. 주어지는 모든 좌표의 절댓값은 10^8 이하이다. N개의 말뚝은 내각이 모두 180도 미만인 볼록 다각형을 이루며, 주어지는 소들의 위치는 밧줄 위에 있지 않다. 또한 각 쿼리에서 N개의 말뚝과 두 소의 좌표는 서로 다르다.

쿼리가 주어진 순서대로 Q개의 줄에 걸쳐 각 쿼리의 답을 한 줄에 하나씩 출력한다.