You are given a connected undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges. Edge $$$i$$$ has a positive integer weight $$$w_i$$$.
In one operation, you may choose one edge and change its weight to any positive integer.
A spanning tree $$$T$$$ of $$$G$$$ is called an $$$x$$$-spanning tree if the greatest common divisor (gcd) of the weights of all edges in $$$T$$$ is divisible by $$$x$$$.
For a given $$$x$$$, Colin wants to know the minimum number of operations required so that $$$G$$$ contains at least one $$$x$$$-spanning tree.
There are $$$k$$$ independent queries. Every query refers to the original graph: the operations considered for one query are not actually performed and do not affect any other query.
Recall that a spanning tree of $$$G$$$ is a connected, acyclic subgraph that contains all $$$n$$$ vertices; it therefore has exactly $$$n-1$$$ edges.
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2\le n\le 10^5$$$, $$$1\le m,k\le 10^5$$$), the number of vertices, edges, and queries, respectively.
Each of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\ne v_i$$$, $$$1\le w_i\le 10^6$$$), denoting an edge of weight $$$w_i$$$ between vertices $$$u_i$$$ and $$$v_i$$$. The graph is guaranteed to be connected.
Each of the next $$$k$$$ lines contains one integer $$$x_i$$$ ($$$1\le x_i\le 10^6$$$), describing the $$$i$$$-th query.
Output $$$k$$$ lines.
The $$$i$$$-th line must contain the minimum number of operations required for the $$$i$$$-th query.
4 6 3 1 2 2 1 3 5 1 4 4 2 3 9 2 4 12 3 4 6 2 3 5
0 1 2
