울타리 감시

국립박물관 전시실에 5000년 된 칼 한 자루가 전시되어 있다. 아주 오래된 이 칼은 박물관이 소장한 유물 가운데 가장 값비싼 축에 든다. 그래서 관람객으로부터 칼을 보호하려고 볼록 다각형 모양의 울타리를 둘러 놓았다. 그런데 경비원 두세 명이 늘 붙어서 지켜야 하니 비용이 만만치 않다.

박물관은 칼과 울타리를 자동으로 지키기로 했다. 울타리를 감시하는 센서를 여러 개 설치하는 방법이다. 센서가 울타리를 제대로 감시하면 울타리는 물론 그 내부까지 또렷하게 볼 수 있다. 박물관이 고른 센서의 성질은 다음과 같다.

1. 센서는 혼자 동작하지 않고 다른 센서와 짝을 이루어 동작한다.
2. 점 $p$와 점 $q$에 놓인 센서 한 쌍은 $\alpha \le \angle pxq \le 360^\circ - \alpha$를 만족하는 점 $x$를 모두 볼 수 있다. 여기서 $0^\circ < \alpha \le 180^\circ$이다.
3. 센서는 바닥 위, 그리고 울타리 경계 위에 놓아야 한다. 바닥의 어떤 점이 감시되면 그 점 바로 위에 있는 점도 모두 감시된다고 본다.

센서가 놓인 점은 그 센서가 감시하는 것으로 본다.

볼록 다각형 모양의 울타리와 $\alpha$ 값이 주어진다. 울타리 경계 위의 모든 점을 감시하는 데 필요한 센서의 최소 개수를 구하여라. 아래 그림은 $\alpha = 120^\circ$일 때의 울타리와 최소 개수의 센서를 배치한 예다. 센서 쌍 $p$, $q$가 감시하는 점은 회색 영역 안의 점뿐이다.

연속한 세 꼭짓점이 한 직선 위에 놓이는 경우는 없다.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 각 테스트 케이스의 첫 줄에는 $\alpha$ ($0 < \alpha \le 180$)와 볼록 다각형의 꼭짓점 개수 $N$ ($3 \le N \le 10000$)이 주어진다. 이어지는 $N$개의 줄에는 꼭짓점의 좌표가 반시계 방향 순서로 한 줄에 하나씩 주어진다. 좌표는 모두 $[-10000, 10000]$ 범위의 값이다. 입력의 모든 값은 정수이고, 한 줄 안의 정수는 공백 하나로 구분한다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 주어진 볼록 다각형의 경계를 제대로 감시하는 데 필요한 센서의 최소 개수를 한 줄에 하나씩 출력한다.