Given a connected undirected graph consisting of vertices and edges, with each edge has a positive integer weight .

In one operation, you can choose an edge and change its weight to any positive integer.

We define a spanning tree of is an -spanning tree if the gcd (greatest common divisior) of the weights of all the edges in  is a multiple of the given number  (i.e.  is a divisor of the gcd) .

Colin wants to ask you that at least how many operations have been executed, there exists at least one -spanning tree  of .

For some secret reason there will be independent queries, please note that every query is based on the initially given graph (i.e. all operations of your answer have not been actually executed) .

Recall that the spanning tree  of the graph is a subgraph which is a tree and contains all vertices of the graph . In other words, it is a connected graph which contains edges and can be obtained by removing some of the edges from .

输入描述:

The first line contains three integers  , representing the number of vertices and edges in  , and the number of queries.

For the following  lines, each line contains three integers  , represents there is an edge in  connects vertices  and  and its weight is  . It's guaranteed that the graph is connected.

For the following  lines, each line contains an integer , representing the -th query.

输出描述:

The output should contains  lines.

For the -th line, output a single integer, representing the minimum number of operations for the -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