There are N island in the Mega Ocean. Ai is the number of people lived in island i. However, all islands are discrete from each other. There is no road transport system between the islands. Though they can travel each other by ship and boats, it is risky as the Pirates of the Mega Ocean create problems like kidnapping, demanding ransom, killing etc. To get rid of this problem permanently, the governments of all these islands decided to make low cost two way tunnels between islands, so that they can visit each other without ship or boats and avoid getting in touch of Pirates of the Mega Ocean. However, the Pirates of the Mega Ocean got the information of tunnel building and sent a letter for all the Government chiefs demanding token money to let the governments building tunnels. According to the letter, the governments have to pay Ax ∗ Ay amount of gold coins to build a tunnel between island x and island y. As the Pirates will not disturb anyone again if they get the money, the governments decided to pay the money. However, the governments of those islands want to spend as less as possible against the pirates. So they decided to build some tunnels in such a way that these tunnels connect all the islands (anyone can travel from any island to another through these tunnels) and the total money given to the pirates is as minimum as possible. However, there is another problem. Some islands are so small that it is impossible to connect more than one tunnel with the island. Given N, A and set of small island S, you have to find the minimum total gold coin you have to give to the pirates to build those tunnels, such that all the islands are connected and small islands are connected to at most one tunnel. Input First line of the input contains a positive integer T (T ≤ 200), the number of test cases. First line of each test case contains two integer numbers N and M (1 ≤ N ≤ 105 and 0 ≤ M < N), denoting the number of island and the number of small islands respectively. Next line contains six integer numbers P, Q, R, X, Y and Z (0 ≤ P,Q,R,X,Y,Z ≤ 105). You have to calculate the number of people Ai for each island using the following equation: Ai =(P ×i2 +Q×i+R)%1000007, 1≤i≤N Similarly, you have to calculate S, the set of small island as follows: Si =(X×i2+Y ×i+Z)%N+1, 1≤i≤M Note that, there can be duplicity in the small island set S. Output For each test case, print the test case number followed by the answer. Explanation: Forbothofthecases,A1 =3,A2 =7andA3 =13. For the first test case, there is no small island, so if you build tunnels A1–A2 and A1–A3, then the total cost will be 7 ∗ 3 + 3 ∗ 13 = 60. For the second test case, the only small island is S1 = 1, so you can’t build multiple tunnels with island 1. If you have to build tunnels A1–A2 and A2–A3, then the total cost will be 7 ∗ 3 + 7 ∗ 13 = 112.
2/2 Sample Input 2 30 111000 31 111000 Sample Output Case 1: 60 Case 2: 112