스파이 네트워크
시간 제한2초메모리 제한256 MB
방향 간선을 따라 값을 gcd로 갱신해 안정 상태에 이른 뒤 값이 L인 직원의 수를 셉니다.
문제
방향 그래프로 표현된 스파이 네트워크에서 정보는 큰 소수의 곱으로 표현된다. 직원이 정보를 받으면 새 정보는 받은 값과 기존 값의 최대공약수로 갱신된다. 더 이상 갱신이 없을 때, 유출된 정보값 을 최종적으로 가진 직원 수를 구하라.
입력
첫 줄에 테스트케이스 수가 주어진다. 각 테스트케이스마다 , , 과 개의 간선, 개의 초기 정보값이 주어진다.
출력
각 테스트케이스마다 최종 상태에서 값이 인 직원 수를 출력한다.