스파이 네트워크

방향 그래프로 표현된 스파이 네트워크에서 정보는 큰 소수의 곱으로 표현된다. 직원이 정보를 받으면 새 정보는 받은 값과 기존 값의 최대공약수로 갱신된다. 더 이상 갱신이 없을 때, 유출된 정보값 $L$을 최종적으로 가진 직원 수를 구하라.

첫 줄에 테스트케이스 수가 주어진다. 각 테스트케이스마다 $N$, $M$, $L$과 $M$개의 간선, $N$개의 초기 정보값이 주어진다.

각 테스트케이스마다 최종 상태에서 값이 $L$인 직원 수를 출력한다.