Suraj a software engineer from Mumbai just got placed in a software company in New Delhi. As, he have to relocate from Mumbai to Delhi, he decided to buy a house. Yeah price of houses have decreased after Narendra Modi became PM of India. He decided to buy a house in a locality which has burger points at each corner. As the streets are only one way there is a heavy traffic jam and it take time to Suraj to reach burger point. Modi just declared that he will convert some streets connecting these burger points to two way roads. Some conversion cost is associated with each street. It will cost lot of money to convert all streets to two way streets so Modi wanted these conversion in such a way that total cost of conversion is minimized keeping in mind that all burger points are connected with two way roads. Suraj after coming to know about this idea decided to buy a house in a two way street. But not all streets will be two way. So, he ask you to tell him if he should buy house in a particular street or not. As there can be more than one conversion plan, help Suraj to decide if he should buy house in that street or not. You will be given m queries by Suraj. Your task is to tell for how many queries will the answer be yes. Return ans in the form of a/b where a is the no. of queries for which ans is yes and b is total number of queries. (gcd(a,b) should be 1).
There will be n burger points and k streets joining them.
[Input format]
First line of input contain 1 integer t denoting no.of test cases.
Next line of input will contain 2 positive integers n and k where n is the no.of burger points and k is the no.of streets connecting them.
Burger points are numbered 1 to n.
Next k line contain 3 positive integers x,y,cst each denoting street between x and y and cst is the cost associated with that street.
Next line contains 1 integer m denoting number of queries.
Next m line contains 2 integers c,d.
[Output Format]
Output answer in the form as specified in ques. For more clarity see sample test case.
[Constraints]
1<=t<=15
1<=n<=1000
1<=cst<=100
k=min(1001, (n*(n-1)/2)) - n) + n
1<=q<=k