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 ci, connecting vertex ai and bi.

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

In the i-th query, he gives you two integers - ui and vi.

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex ui and vertex vi directly or indirectly.

Input

The first line of the input contains space-separated two integers - n and m(2 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting the number of the vertices and the number of the edges, respectively.

The next m lines contain space-separated three integers - ai, bi(1 ≤ ai < bi ≤ n) and ci(1 ≤ ci ≤ 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, (ai, bi, ci) ≠ (aj, bj, cj).

The next line contains a integer- q(1 ≤ q ≤ 105), denoting the number of the queries.

Then follows q lines, containing space-separated two integers - ui and vi(1 ≤ ui, vi ≤ n). It is guaranteed that ui ≠ vi.

Output

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

Examples

Input

4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4


Output

2
1
0


Input

5 7
1 5 1
2 5 1
3 5 1
4 5 1
1 2 2
2 3 2
3 4 2
5
1 5
5 1
2 5
1 5
1 4


Output

1
1
1
1
2

Note

Let's consider the first sample. 

<image> 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. 
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
public class Solution 
{
    public static int n,m;
    public static ArrayList<node>[] al;
    public static boolean[] vis;
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    public static class node 
    {
        int val;
        int col;
        boolean vis;
        node(int a0,int a1)
        {
            val=a0;
            col=a1;
        }
    }
    
    public static boolean bfs(int s,int d,int c)
    {
        ArrayDeque<node> qu=new ArrayDeque<node>();
        node nd=new node(s,0);
        nd.vis=true;
        qu.add(nd);
        //System.out.println(nd.val);
        while(!qu.isEmpty())
        {
            node n1=qu.remove();
            for(int i=0;i<al[n1.val].size();i++)
            {    
                if(vis[al[n1.val].get(i).val]==false && al[n1.val].get(i).col==c)
                {
                    //System.out.println(c+" "+al[n1.val].get(i).val);
                    qu.add(al[n1.val].get(i));
                    vis[al[n1.val].get(i).val]=true;
                    if(al[n1.val].get(i).val==d)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    @SuppressWarnings("unchecked")
     public static void main(String[] args) throws Exception
     {
         Reader rd=new Reader();
         n=rd.nextInt();
         m=rd.nextInt();
         al=new ArrayList[n+1];
         for(int i=0;i<=n;i++)
         {
             al[i]=new ArrayList<node>();
         }
         boolean[] clr=new boolean[m+1];
         int di=0;
         for(int i=0;i<m;i++)
         {
             int v1=rd.nextInt();
             int v2=rd.nextInt();
             int c=rd.nextInt();
             if(clr[c]==false)
             {
                 di++;
                 clr[c]=true;
             }
             al[v1].add(new node(v2,c));
             al[v2].add(new node(v1,c));
         }
         vis=new boolean[n+1];
         int q=rd.nextInt();
         for(int i=0;i<q;i++)
         {
             int count=0;
             int s=rd.nextInt();
             int d=rd.nextInt();
             for(int j=1;j<=m;j++)
             {
                if(clr[j]==true)
                {
                    Arrays.fill(vis,false);
                    if(bfs(s,d,j))
                    {
                        count++;
                    }
                }
             }
             System.out.println(count);
         }
     }
}   