Mr. Kitayuta has just bought an undirected graph with $*n*$ vertices and $*m*$ edges. The vertices of the graph are numbered from 1 to $*n*$. Each edge, namely edge $*i*$, has a color $*c*_{*i*}$, connecting vertex $*a*_{*i*}$ and $*b*_{*i*}$.

Mr. Kitayuta wants you to process the following $*q*$ queries.

In the $*i*$-th query, he gives you two integers - $*u*_{*i*}$ and $*v*_{*i*}$.

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex $*u*_{*i*}$ and vertex $*v*_{*i*}$ directly or indirectly.

Input

The first line of the input contains space-separated two integers - $*n*$ and $*m*(2 ≤ *n* ≤ 10^{5}, 1 ≤ *m* ≤ 10^{5})$, denoting the number of the vertices and the number of the edges, respectively.

The next $*m*$ lines contain space-separated three integers - $*a*_{*i*}$, $*b*_{*i*}(1 ≤ *a*_{*i*} < *b*_{*i*} ≤ *n*)$ and $*c*_{*i*}(1 ≤ *c*_{*i*} ≤ *m*)$. Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if $*i* ≠ *j*, (*a*_{*i*}, *b*_{*i*}, *c*_{*i*}) ≠ (*a*_{*j*}, *b*_{*j*}, *c*_{*j*})$.

The next line contains a integer- $*q*(1 ≤ *q* ≤ 10^{5})$, denoting the number of the queries.

Then follows $*q*$ lines, containing space-separated two integers - $*u*_{*i*}$ and $*v*_{*i*}(1 ≤ *u*_{*i*}, *v*_{*i*} ≤ *n*)$. It is guaranteed that $*u*_{*i*} ≠ *v*_{*i*}$.

Output

For each query, print the answer in a separate line.

Note

Let's consider the first sample.

The figure above shows the first sample.

• Vertex $1$ and vertex $2$ are connected by color $1$ and $2$.
• Vertex $3$ and vertex $4$ are connected by color $3$.
• Vertex $1$ and vertex $4$ are not connected by any single color.