시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 5 3 3 60.000%

문제

NSA가 아주 짱짱 큰 정수를 소인수분해하는 알고리즘을 발견했다! 그들은 조직 내의 spy network에서 암호화된 메시지를 주고받는 데 이 알고리즘을 적극 활용하기로 하였다. 그들의 spy network는 방향 그래프 G = (V, E)의 형태로 표현될 수 있으며, 각 정점은 NSA의 직원을 의미하고 각 간선 (u, v)는 u가 v에게 비밀스럽게 정보를 보낼 수 있음을 의미하며, 이는 v가 u의 연락망에 속해 있다고도 표현할 수 있다. u가 v에게 정보를 보낼 수 있다고 해서 v가 u에게 정보를 보낼 수 있지는 않다는 것에 주의하라.

NSA의 직원들은 항상 알려진 테러 조직들의 테러 조짐을 관찰하고 있으며 몇 달의 기한마다 동료들에게 어떤 테러 조직이 테러를 일으킬 조짐이 보이는지를 보고한다.

정보 전달 방식은 이렇다.

  1. 모든 직원들은 자신이 모은 정보를 자신의 연락망에 속한 다른 직원들에게 보낸다.
  2. 만약 어떤 직원이 정보 ireceived를 받았다면, 자신이 지금까지 가지고 있던 정보 iold와 결합하여 새로운 정보 inew를 생성하고, 그것을 자신의 최신 정보로 대체한다.
  3. 이때, inew는 ireceived와 iold에 모두 포함되어 있던 정보만으로 생성된다. 이는 워낙에 NSA에 거짓 정보가 많이 흘러들어오기에, 여러 직원이 발견하지 못했다면 진실이라는 당위성이 떨어진다고 판단하기로 했기 때문이다.
  4. 그 다음부터 해당 직원이 다른 직원에게 보낼 정보는 inew이다.

모든 직원들은 정보를 전달할 때 이런 과정을 따른다.

만약 직원들이 정보를 계속해서 주고받으면, 어느 순간부터 아무리 정보를 보내도 그 어떤 정보도 갱신되지 않는 일이 발생한다. 이때 모든 직원들은 정보 송신을 그만둔다. Spy network 전체가 연결되어 있지 않을 수도 있고, 싸이클이 존재할 수도 있음에 유의하라.

NSA는 이러한 정보의 형태를 큰 소수의 곱으로 나타내기로 했다. 모든 테러 조직마다 대응하는 큰 소수값을 부여한 후(다른 조직은 다른 값을 부여받는다), 여러 조직을 표현하는 정보는 그 소수들의 곱으로 나타낸다. 만약 어떤 사원이 ireceived를 받았다면, inew는 ireceived와 iold의 최대공약수(greatest common divisor)가 될 것이다. 왜냐하면 두 정보의 최대공약수가 두 정보에 모두 포함되어 있는 소수들만의 곱이기 때문이다. 이렇게 정보를 전달하다가 정보 송신이 중단된 경우, 어떤 직원은 중요한 상황에 소인수분해 알고리즘을 사용하여 조직의 정보를 파악할 수 있다.

NSA는 최근에 자신들의 정보가 외부로 유출되었음을 확인했다! 모든 정보는 암호화되어 있고 잃어버린 정보 또한 없지만, NSA는 정보 유출자를 찾아내기로 결정했다. 이에 당신의 도움이 필요하다. 정확히 누가 정보를 유출했는지는 알 수 없지만, NSA는 유출된 정보의 값을 알고 있었다. 만약 spy network가 더 이상의 어떠한 정보 갱신도 이루어지지 않는 상태가 되었을 때, 유출된 정보의 값을 가지고 있던 직원들이 누구인지를 아는 것부터 시작하기로 했다. 그렇게 한다면 수색망을 좁힐 수 있기 때문이다.

최종 상태에서 누출된 정보값을 가지고 있는 직원의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 첫 번째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 N, M, L이 주어진다. (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 10 000, 1 ≤ l < 263) N은 직원의 수, M은 간선의 수, L은 누출된 정보값을 의미한다.

이어지는 M개의 줄에 간선의 정보가 하나씩 주어진다. 한 줄에 두 정수 a, b가 주어지는데, 이는 b가 a의 연락망에 속해 있음을 의미한다. (1 ≤ a, b ≤ n, a ≠ b)

이어지는 N개의 줄에 각 직원이 처음에 가지고 있던 정보값 i가 주어진다. (1 ≤ i < 263)

출력

각 테스트 케이스마다 한 줄에 걸쳐서 최종 상태에서 누출된 정보값을 가지고 있던 직원의 수를 출력한다.

예제 입력

3
4 3 7
1 3
2 3
3 4
35
77
385
385
4 4 159
1 2
2 3
3 1
4 1
159
159
159
2014
5 5 9
2 1
2 3
3 2
3 4
5 4
27
54
90
315
135

예제 출력

2
0
2

힌트

첫 번째 테스트 케이스의 spy network이다.