This page is still under construction.

Parts of this page are still being built. What you see may change.

Spy Network

Time limit2sMemory limit256 MB

Summary
Values spread along directed edges by repeated gcd updates until stable, and you count how many employees end at L.
Level

Medium7 of 10

Topics
Graph, Topological sort, Number theory
Solved
No attempts yet

Problem

In a directed spy network, each employee holds an integer information value. When employee a sends to b, employee b replaces their value with gcd(received, old). Propagation continues until stable. Count how many employees end with the leaked value LL.

Input

The first line contains the number of test cases. Each test case gives NN, MM, LL, then MM directed edges and NN initial values.

Output

For each test case, print how many employees hold value LL in the final stable state.

Examples1

  1. Example 1

    Input
    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
    Expected output
    2
0
2