온도계

당신은 한 섬의 해안을 따라 형성된 기후를 조사하는 연구팀의 일원이다. 섬의 해안은 둘레가 K킬로미터인 원으로 모델링된다. 해안에는 원의 둘레 위 한 점을 차지하는 등대가 있다. 해안의 각 점은 [0, K) 범위의 실수에 대응된다. 엄밀히 말해, 점 x는 해안을 따라 시계 방향으로 걸을 때 등대에서 x킬로미터 떨어진 해안의 점이다. 예를 들어, K = 5이면 점 0은 등대가 있는 점이고, 점 1.5은 시계 방향으로 등대에서 1.5킬로미터 떨어진 점이며, 점 2.5은 등대의 지름상 반대편에 있는 점이다.

당신은 해안의 온도를 연구하는 일을 담당한다. 다른 팀이 다음과 같이 작동하는 해안 온도 측정 시스템을 설치했다. 특정 지점들의 온도를 측정하기 위해 여러 개의 온도계를 해당 지점들에 배치했다. 같은 지점에 두 개의 온도계를 배치하지는 않았다. 그 팀의 모델에서는 온도계가 없는 점의 온도가 가장 가까운 온도계에서 측정된 온도와 같다고 가정한다. 두 온도계에서 같은 거리에 있는 점에는 시계 방향에 있는 온도계, 즉 그 점에서 시계 방향으로 걸을 때 가장 먼저 마주치는 온도계를 사용한다.

안타깝게도 시스템이 사용한 온도계의 개수나 배치된 위치는 알 수 없지만, 시스템의 온도 데이터에는 접근할 수 있다. 이 데이터는 각각 N개의 값으로 이루어진 두 목록 $X_{1}$, $X_{2}$, ..., $X_{N}$와 $T_{1}$, $T_{2}$, ..., $T_{N}$로 주어진다. 이는 각 1 ≤ i < N에 대해 $X_{i}$ ≤ x < $X_{i+1}$인 각 점 x에 온도 $T_{i}$가 할당되고, 0 ≤ x < $X_{1}$ 또는 $X_{N}$ ≤ x < K인 각 점 x에 온도 $T_{N}$가 할당됨을 나타낸다. 점들은 시계 방향으로 열거되어 있으므로 모든 i에 대해 $X_{i}$ < $X_{i+1}$이다.

어떤 위치들의 집합에 배치했을 때 관측된 데이터를 만들어 낼 수 있는 온도계의 최소 개수를 구하려고 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 2 ≤ N ≤ min(100, K). 0 ≤ $X_{1}$. 모든 i에 대해 $X_{i}$ < $X_{i+1}$. $X_{N}$ < K. 모든 i에 대해 184 ≤ $T_{i}$ ≤ 330. 모든 i에 대해 $T_{i}$ ≠ $T_{i+1}$. $T_{1}$ ≠ $T_{N}$.

테스트 세트 1 (Visible Verdict)

2 ≤ K ≤ 10.

테스트 세트 2 (Hidden Verdict)

2 ≤ K ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 세 줄로 이루어진다. 테스트 케이스의 첫 줄에는 섬의 둘레와 온도 데이터를 나타내는 목록의 크기인 두 정수 K와 N이 주어진다. 둘째 줄에는 N개의 정수 $X_{1}$, $X_{2}$, ..., $X_{N}$가 주어진다. 셋째 줄에는 N개의 정수 $T_{1}$, $T_{2}$, ..., $T_{N}$가 주어진다. 둘째 줄과 셋째 줄의 정수들이 온도를 나타내는 방식은 위에서 설명했다.

각 테스트 케이스에 대해 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며 1부터 시작하고, y은 위에서 설명한 대로 관측된 입력 데이터를 만들어 낼 수 있는 온도계의 최소 개수이다.

예제 케이스 #1에서는 서로 다른 두 온도가 측정되었으므로 적어도 2개의 온도계가 필요하다. 점 0.5에 온도 184를 측정하는 온도계 하나를 두고 점 1.5에 온도 330를 측정하는 또 다른 온도계를 두면, 정확히 2개의 온도계로 데이터를 만들어 낼 수 있다. 점 0과 점 1은 두 온도계에서 같은 거리에 있으므로 시계 방향에 있는 온도계를 사용한다는 점에 유의하라. 점 0에서 측정된 온도는 점 0.5의 온도계에서 오고, 점 1에서 측정된 온도는 점 1.5의 온도계에서 온다.

예제 케이스 #2의 데이터는 온도계 2개만으로는 만들어 낼 수 없다. 점 0.2, 점 1.8, 점 2.8에 온도계를 배치하여 각각 184, 330, 330을 측정하게 하면 3개의 온도계로 데이터를 만들어 낼 수 있다. 입력 데이터를 만들어 내도록 3개의 온도계를 배치하는 다른 방법들도 있다.

예제 케이스 #3에서 3개의 온도계로 데이터를 만들어 내는 한 가지 방법은 점 0, 점 2, 점 8에 온도계를 배치하여 각각 330, 184, 200을 측정하게 하는 것이다.