candyshop

Problem Description

Jack is a little boy with big dreams: to own the biggest candy shop in the world! He's off to a modest start with N candies for sale, numbered from 0 to N - 1. The price of candy i is i dollars. In his shop's front window, Jack has arranged his candies in the shape of a tree rooted at candy 0, with the parent of each other candy i (1 ≤ i < N) being candy Pi.

M other kids in Jack's neighbourhood have agreed to come by and be his first customers! Jack has assigned them customer numbers from 0 to M - 1. Unfortunately, these kids are a bit picky when it comes to sweets. Customer i only likes candies within the subtree rooted at candy Ci. This means that they're only willing to purchase a candy if it's either candy Ci, or one of its children, or one of its childrens' children, and so on. They also have amazing self-restraint — each customer will limit themselves to buying at most one candy.

For each of the M customers, Jack may either sell them any single candy of his choice within the customer's required subtree, or no candy at all. Each of the N candies may be sold to at most one customer. Jack is willing to do whatever it takes to achieve his dreams, even if it means extorting as much cash as possible from fellow children. As such, he'd like to choose candies to sell such that the sum of their prices is maximized. Can you help him determine this maximum sum of candy prices?

In order to reduce the size of the input data, C0..M-1 may be generated as follows using given constants A and B:

Ci = (A * i + B) % N (for i = 0 .. M - 1)

Input

Input begins with an integer T, the number of trees. For each tree, there is first a line containing the space-separated integers N, M, A, and B. Then N - 1 lines follow, the ith of which (1-indexed) contains the single integer Pi.

Output

For the ith tree, output a line containing "Case #i: " followed by the maximum possible sum of prices of candies which Jack can sell.

Constraints

1 ≤ T ≤ 110
1 ≤ N ≤ 200,000
0 ≤ M ≤ 1,000,000
0 ≤ A, B, Pi, Ci < N
It is guaranteed that each test case describes a single valid tree rooted at candy 0.

Explanation of Sample

In the first case, C = [0]. The only customer can be sold any candy in candy 0's subtree, which includes candies 0 and 1. Jack should choose to sell them candy 1, which has a price of 1 dollar.
In the second case, C = [2, 0, 2]. Jack should sell candy 2 to customer 0, candy 3 to customer 1, and no candy to customer 2. The sum of these candy prices is 2 + 3 = 5 dollars.
In the third case, C = [4, 6, 0, 2].

Sample Input

4
2 1 1 0
0
4 3 2 2
3
0
0
8 4 2 4
0
1
0
0
7
1
4
20 14 6 6
5
4
8
0
2
11
18
4
4
11
4
5
6
8
13
3
6
5
15

Sample Output

Case #1: 1
Case #2: 5
Case #3: 20
Case #4: 165