GBus 수 세기

직선 도로를 따라 건설된 몇몇 도시가 있다. 도시는 왼쪽에서 오른쪽으로 1, 2, 3...의 번호가 매겨져 있다.

이 도로를 따라 운행하는 N GBuses가 있다. 각 GBus에 대해 그 버스가 운행하는 도시의 범위를 알고 있다. i번째 GBus는 번호가 $A_{i}$ 이상 $B_{i}$ 이하인 도시들을 운행한다.

우리는 P개 도시로 이루어진 특정 부분집합에 관심이 있다. 이 도시 각각에 대해 해당 도시를 운행하는 GBus가 몇 대인지 구해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 10.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 50 모든 i에 대해 1 ≤ $A_{i}$ ≤ 500. 모든 i에 대해 1 ≤ $B_{i}$ ≤ 500. 모든 i에 대해 1 ≤ $C_{i}$ ≤ 500. 1 ≤ P ≤ 50.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 500. 모든 i에 대해 1 ≤ $A_{i}$ ≤ 5000. 모든 i에 대해 1 ≤ $B_{i}$ ≤ 5000. 모든 i에 대해 1 ≤ $C_{i}$ ≤ 5000. 1 ≤ P ≤ 500.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 케이스와 다음 케이스 사이에는 빈 줄이 하나 있다. (Kickstart 데이터 세트에서는 이례적인 형식임에 유의한다.)

각 테스트 케이스에서:

• 첫 번째 줄에는 GBus의 수를 나타내는 정수 N 하나가 주어진다.

• 두 번째 줄에는 버스가 운행하는 도시의 범위를 $A_{1}$ $B_{1}$ $A_{2}$ $B_{2}$ $A_{3}$ $B_{3}$ ... $A_{N}$ $B_{N}$ 형식으로 나타내는 2N개의 정수가 주어진다. 즉, 첫 번째 GBus는 번호가 $A_{1}$부터 $B_{1}$까지인 도시들을 운행하며(양 끝 포함), 이후도 같은 방식이다.

• 세 번째 줄에는 위에서 설명한 관심 대상 도시의 수를 나타내는 정수 P 하나가 주어진다. (이는 문제에 주어지지 않는 전체 도시 수와 반드시 같지는 않다는 점에 유의한다.)

• 마지막으로 P개의 줄이 더 주어지며, 이 중 i번째 줄에는 관심 대상 도시의 번호 $C_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 P개의 정수로 이루어진 목록이며, 이 목록의 i번째 정수는 도시 $C_{i}$를 운행하는 GBus의 수이다.

예제 케이스 #1에는 GBus가 넷 있다. 첫 번째 버스는 도시 15부터 25까지, 두 번째 버스는 도시 30부터 35까지, 세 번째 버스는 도시 45부터 50까지, 네 번째 버스는 도시 10부터 20까지 운행한다. 도시 15는 첫 번째와 네 번째 버스가 운행하므로, 답 목록의 첫 번째 수는 2이다. 도시 25는 첫 번째 버스만 운행하므로, 답 목록의 두 번째 수는 1이다.