공정한 대결

앙 가르드! Charles와 Delila가 Swordmaster 펜싱 대회의 결승전에서 서로 맞붙으려 한다.

펜싱 경기장의 한쪽 벽을 따라 N가지 서로 다른 종류의 검이 놓인 선반이 있다. 검의 종류에는 1부터 N까지 번호가 매겨져 있다. 수석 심판인 당신은 정수 쌍 (L, R)을 하나 고르며(이때 1 ≤ L ≤ R ≤ N), L번째부터 R번째까지의 검 종류만 양 끝을 포함하여 대결에 사용할 수 있다.

서로 다른 종류의 검은 서로 다른 방식으로 사용하며, 한 종류의 검을 잘 다룬다고 해서 반드시 다른 종류의 검도 잘 다루는 것은 아니다! i번째 종류의 검에 대한 Charles와 Delila의 숙련도는 각각 $C_{i}$와 $D_{i}$이다. 두 사람은 각자 당신이 이 대결에 사용할 수 있게 한 검의 종류들을 살펴본 다음, 자신이 가장 능숙하게 다루는 종류를 선택한다. 어떤 선수가 똑같이 능숙하게 다루는 사용 가능한 종류가 여러 개이고 그 숙련도가 사용 가능한 다른 모든 종류에 대한 그 선수의 숙련도보다 높다면, 그 선수는 똑같이 좋은 선택지 중 하나를 무작위로 고른다. Charles와 Delila가 같은 종류의 검을 선택할 수도 있으며, 이는 문제없다는 점에 유의한다. 각 종류의 검은 여러 자루 준비되어 있다.

Charles가 선택한 검 종류에 대한 숙련도와 Delila가 선택한 검 종류에 대한 숙련도의 절댓값 차이가 최대 K이면 대결은 공정하다. 대결의 흥미를 유지하기 위해, 공정한 대결이 되게 하는 서로 다른 (L, R) 쌍을 몇 개 선택할 수 있는지 알고자 한다.

제한

1 ≤ T ≤ 100. 0 ≤ K ≤ $10^{5}$. 0 ≤ $C_{i}$ ≤ $10^{5}$, 모든 i에 대해. 0 ≤ $D_{i}$ ≤ $10^{5}$, 모든 i에 대해. 시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

1 ≤ N ≤ 100.

테스트 세트 2 (비공개)

정확히 8개의 테스트 케이스에 대해 N = $10^{5}$. 8개의 테스트 케이스를 제외한 모든 테스트 케이스에 대해 1 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 위에서 설명한 두 정수 N과 K가 담긴 한 줄로 시작한다. 그다음 두 줄이 더 주어진다. 이 중 첫 번째 줄에는 위에서 설명한 각 검 종류에 대한 Charles의 숙련도를 나타내는 N개의 정수 $C_{i}$가 주어진다. 마찬가지로 두 번째 줄에는 Delila의 숙련도를 나타내는 N개의 정수 $D_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y를 담은 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 공정한 대결이 되게 하는 선택의 수이다.

예제 케이스 #1에서는 Charles가 마지막 종류의 검을 사용할 수 있을 때, 그리고 그럴 때에만 대결이 공정하므로 답은 4이다.

예제 케이스 #2에는 공정한 대결이 4개 있다. (1, 2), (1, 3), (2, 2), (2, 3)이다. (1, 3) 같은 쌍에서는 Charles와 Delila가 각자 자신이 가장 능숙하게 다루는 검을 여러 자루 중에서 선택할 수 있지만, 각 쌍은 공정한 대결 하나로만 센다는 점에 유의한다.

예제 케이스 #3에는 공정한 대결이 1개 있다. (1, 1)이다.

예제 케이스 #4에는 공정한 대결이 없으므로 답은 0이다.

예제 케이스 #5에서는 결투자들이 대결을 공정하게 만들려고 하는 것이 아니라 자신이 가장 능숙하게 다루는 검 종류를 선택한다는 점을 기억해야 한다. 예를 들어 (1, 3)는 공정한 대결이 아니다. Charles는 첫 번째 종류의 검을 선택하고 Delila는 세 번째 종류의 검을 선택하기 때문이다. Delila는 더 약한 검을 골라 Charles를 봐주지 않는다!

예제 케이스 #6에는 공정한 대결이 7개 있다. (1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)이다.