You must have heard the "Traveling Salesman Problem". Here we are talking about another problem named "Traveling Fool Problem". Assume that there are \textbf{n} cities connected by \textbf{m} one way roads. Each road is labeled by an uppercase English letter (i.e '\textbf{A}' to '\textbf{Z}'). There can be multiple roads between two cities but no roads will start and end at the same city. The traveling fool starts his journey from city s and he continues his journey until he reaches \textbf{t}, or he reaches a city from which \textbf{t} is unreachable. If he is in city \textbf{u}, he can choose any road that starts from \textbf{u} with equal probability. He may visit same city/road more than once, but once he reaches \textbf{t}, he immediately stops his journey and remembers the road-labels he found in his path in the same order the roads were visited. If the road-labels in the path he traveled form a palindrome, he finds himself lucky. If he is unable to reach \textbf{t} or the road-labels don’t form a valid palindrome, he finds himself unlucky. Given the cities, roads, \textbf{s} and \textbf{t}, can you find the probability of Mr Traveling Fool being lucky? \InputFile Input starts with an integer \textbf{T} (≤ \textbf{100}), denoting the number of test cases. Each case starts with a blank line. Next line contains two integers \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{12}) and \textbf{m} (\textbf{0} ≤ \textbf{m} ≤ \textbf{1000}). Each of the next \textbf{m} lines contains two integers, \textbf{u v} (\textbf{0} ≤ \textbf{u}, \textbf{v} < \textbf{n}, \textbf{u} ≠ \textbf{v}) and an uppercase English letter \textbf{w}, meaning that there is a one-way road from city \textbf{u} to city \textbf{v} and the road label is \textbf{w}. Next line contains an integer (\textbf{1} ≤ \textbf{q} ≤ \textbf{150}) denoting the number of queries. Each of the next \textbf{q} lines contains two integers denoting \textbf{s t} (\textbf{0} ≤ \textbf{s}, \textbf{t} < \textbf{n}, \textbf{s} ≠ \textbf{t}). \OutputFile For each case, print the case number first. Then for each query, print the probability as stated. Errors less than \textbf{10^\{-4 \}}will be ignored.