Percy is a harlequin tuskfish who lives on a stretch of the sea floor, which
may be represented as a number line. There are **N** objects resting on the
sand beneath the waves, the _i_th of which is at a positive integral position
**Pi**, is either a clam (if **Oi** = "C") or otherwise a rock (if **Oi** =
"R"), and in either case has a hardness of **Hi**. No two objects are at the
same position, and at least one of the objects is a clam.

Percy initially finds himself at position 0, and can then swim in either
direction along the number line at a rate of 1 unit per second. Whenever he
occupies the same position as a clam, he may pick it up and begin carrying it
around in his mouth. Picking up a clam requires no additional time, and Percy
is talented enough to carry any number of clams at once.

Percy would like to devour the delicious interior of each clam, but can't get
to it without first somehow breaking open its hard shell. Fortunately, Percy
is clever and persistent enough to have a
[solution](https://www.radiotimes.com/news/2018-01-26/blue-planet-2-fish-
clams-tools/) to this problem. Whenever he occupies the same position as a
rock, he may take each clam that he's currently carrying that has a strictly
smaller hardness than that of the rock, knock the clam against the rock to
break open its shell, and eat the meal packaged within! This process requires
no additional time per clam.

What's the minimum amount of time required for Percy to swim around and eat
all of the clams (by picking each one up and then knocking it against a harder
rock than itself), if at all possible?

In order to reduce the size of the input, the object's positions and
hardnesses will not all be provided explicitly. Instead, you'll be given
**P1**, **P2**, **H1**, **H2**, as well as the 8 constants **Ap**, **Bp**,
**Cp**, **Dp**, **Ah**, **Bh**, **Ch**, and **Dh**, and must then compute
**P3..N** and **H3..N** as follows (bearing in mind that intermediate values
may not fit within 32-bit integers):

**Pi** = ((**Ap** * **Pi-2** \+ **Bp** * **Pi-1** \+ **Cp**) modulo **Dp**) + 1, for _i_ = 3 to **N**.

**Hi** = ((**Ah** * **Hi-2** \+ **Bh** * **Hi-1** \+ **Ch**) modulo **Dh**) + 1, for _i_ = 3 to **N**.

### Input

Input begins with an integer **T**, the number of days Percy goes hunting for
clams. For each day, there are four lines. The first line contains the integer
**N**. The second line contains the space-separated integers **P1**, **P2**,
**Ap**, **Bp**, **Cp**, and **Dp**. The third line contains the space-
separated integers **H1**, **H2**, **Ah**, **Bh**, **Ch**, and **Dh**. The
fourth line contains the length-**N** string **O1..N**.

### Output

For the _i_th day, print a line containing "Case #_i_: " followed by one
integer, either the minimum number of seconds required for Percy to break open
and eat all of the clams, or -1 if he cannot do so.

### Constraints

1 ≤ **T** ≤ 250
2 ≤ **N** ≤ 800,000
0 ≤ **Ap**, **Bp**, **Cp**, **Ah**, **Bh**, **Ch** ≤ 1,000,000,000
1 ≤ **Dp**, **Dh** ≤ 1,000,000,000
1 ≤ **Pi** ≤ **Dp**
1 ≤ **Hi** ≤ **Dh**

### Explanation of Sample

In the first case, P = [5, 10] and H = [30, 31]. Percy should swim to position
5, pick up the clam with hardness 30, swim onwards to position 10, and break
open the clam on the rock with hardness 31.

In the second case, P = [5, 10] and H = [31, 30]. Percy should now swim to
position 10 to pick up the clam, and then back to position 5 to break it open.

In the third case, P = [5, 10] and H = [30, 30]. Once Percy picks up the clam,
no rock harder than it exists on the sea floor, meaning that he can never
break it open.

In the fourth case, P = [10, 50, 11, 52] and H = [50, 10, 49, 8].

In the fifth case, P = [415, 711, 225, 136, 256, 469, 714, 399, 841, 697, 480,
147, 98, 837, 745, 660, 44, 226, 73, 7] and H = [9, 2, 10, 6, 6, 2, 7, 13, 4,
5, 11, 11, 4, 3, 7, 1, 6, 10, 10, 1].