Description
Bridges is a company who provides delivery service. Their policy of determining the shipping cost is to sum up the cost along the edges from the source logistic center to the target logistic center.
The following graph is an example of their delivery route map.
Suppose the closest logistic center from the place where customer A lives is number 0. If customer A wants to send his package to customer B, who lives near by the logistic center number 4, the cheapest shipping path will be :
logistic center number 0 -> logistic center number 2 -> logistic center number 3 -> logistic center number 4. The cost will be 33.
Now, Bridges, the company, wants to develop a program which can help their costumers to know the cost of the cheapest shipping path based on the query they input.
The query contains two numbers. The first one represents the source logistic center, and the second one represents the target logistic center.
For example, considered the route map above, input the query
0 4
The output of this query will be
Cost(0,4):33
Please help Bridges to develop the program.
Input
The first line of the input will contain a number T (2<=T<=10), which means the number of the testcases.
For each testcase, the first line contain a number N(5<=N<=100), which means the number of nodes (logistic centers) in the route map.
The second line will contain a number Q(5<=Q<=1000), which means the number of the queries.
And then, an NxN matrix will be given, which represents the route map.
For example, the following matrix represent the example route map.
| 0 | 10 | 4 | 0 | 0 |
| 0 | 0 | 0 | 4 | 0 |
| 0 | 0 | 0 | 9 | 0 |
| 0 | 0 | 0 | 0 | 20 |
| 0 | 15 | 0 | 0 | 0 |
In the matrix, 0 means that there are no edges between the two nodes. Namely, the packages can not be delivered between the two nodes. Non-zero digit in the matrix means there is a directed edges between the two nodes, and the value of the digit means the cost.
The digit in the matrix will be 0 <= digit <= 20.
Finally, Q queries will be input. Each query contains two numbers. The first number represents the source logistic center, and the second one represents the target logistic center. For each query, the first number ≠ the second number.
Output
For each testcase, first output Testcaset (t∈{1,2,...,T})
And then, according to the queries, output the corresponding cost.
Cost(source,target):xxx
Constraints:
- If there are no paths from the source to the target, you need to output:
- Cost(source,target):No Service
