책 읽기

Supervin은 1부터 N까지 번호가 매겨진 N쪽의 고대 서적을 관리하는 사서이다. 책이 너무 오래되어 안타깝게도 M쪽이 찢겨 나갔다. 그 페이지 번호는 $P_{1}$, $P_{2}$, ..., $P_{M}$이다.

오늘 이 고대 서적을 읽는 데 관심이 있는 게으른 독자 Q명이 있다. 이들은 게으르기 때문에 각 독자가 반드시 모든 페이지를 읽는 것은 아니다. 대신 i번째 독자는 페이지 번호가 $R_{i}$의 배수이면서 찢겨 나가지 않은 페이지만 읽는다. Supervin은 각 독자가 읽는 페이지 수의 합을 알고 싶다.

제한

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $P_{1}$ < $P_{2}$ < ... < $P_{M}$ ≤ N. 모든 i에 대해 1 ≤ $R_{i}$ ≤ N.

테스트 세트 1 (공개)

1 ≤ M ≤ N ≤ 1000. 1 ≤ Q ≤ 1000.

테스트 세트 2 (비공개)

1 ≤ M ≤ N ≤ $10^{5}$. 1 ≤ Q ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 책의 페이지 수, 책에서 찢겨 나간 페이지 수, 독자 수를 각각 나타내는 세 정수 N, M, Q가 포함된 줄로 시작한다. 두 번째 줄에는 M개의 정수가 주어지며, 이 중 i번째 정수는 $P_{i}$이다. 세 번째 줄에는 Q개의 정수가 주어지며, 이 중 i번째 정수는 $R_{i}$이다.

각 테스트 케이스에 대해 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이고(1부터 시작), y은 모든 독자가 읽게 될 페이지 수의 총합이다.

예제 케이스 #1에서 첫 번째 독자는 번호가 2, 4, 6, 10인 페이지를 읽는다. 번호가 8인 페이지는 찢겨 나갔으므로 읽지 않는다는 점에 유의하라. 두 번째 독자는 번호가 3, 6, 9인 페이지를 읽는다. 따라서 모든 독자가 읽게 될 페이지 수의 총합은 4 + 3 = 7이다.

예제 케이스 #2에서는 모든 페이지가 찢겨 나갔으므로 모든 독자가 0쪽을 읽는다.

예제 케이스 #3에서 첫 번째 독자는 주어진 여섯 페이지를 제외한 모든 페이지를 읽는다.