Werewolf Scribes (part 2)

Note: This problem statement is identical to Werewolf Scribes (part 1), but has a higher limit on $N$ .

A strange sickness has spread through the villages: lycanthropy.
Each night, one villager is turned into a werewolf. He gains a certain strength and must join a clan.

Every morning, the scribes of the realm record the median strength of all werewolves for chronicling purposes.

Clans

Clans are denoted with digits 0–9.
You are given a string $S$ that describes the clan pattern:
- On night 1, the new werewolf joins the clan given by the first character of $S$ .
- On night 2, the clan given by the second character of $S$ .
- This continues through all characters of $S$ .
- After reaching the end of $S$ , the pattern repeats from the beginning.
The clans that exist are exactly the digits that appear in the string $S$ .

Strength

The initial strength of the werewolf on night $i$ is $X_{i}$ , defined by the recurrence:

$X_{0} = 0$ (seed).
For $i \geq 1$ ,
$X_{i} = (X_{i - 1} \cdot A + B) mod 2^{20}$ .

Every $M$ nights, a blood moon occurs. On such nights (i.e., when the night number is divisible by $M$ ), after the new werewolf joins their clan, every member of that clan (including the newcomer) gains 1 additional strength.

Scribing

After each night, consider the multiset of strengths of all werewolves turned so far. The median is defined as:

If the number of werewolves is odd, the middle element.
If the number is even, the lower median (the smaller of the two middle elements).

Your task is to compute the sum of the medians recorded after the first $N$ nights.

Constraints

$1 \leq N \leq 1, 000, 000$
$0 \leq A, B < 2^{20}$
$1 \leq M \leq 100$
$1 \leq ∣ S ∣ \leq 100$
$S$ consists of 0–9 digits only.

Input

The first line contains an integer $T$ , the number of test cases.
Each of the next $T$ lines contains integers $N, A, B, M$ , followed by a nonempty string $S$ of digits (0–9).

Output

For each test case, print a line in the format Case #i: ans, where ans is the sum of medians from night 1 through night $N$ .

Example

Input

2
4 2 5 3 21
5 131072 8 1 7

Output

Case #1: 40
Case #2: 49

Explanation

Case 1.

Parameters: $N = 4$ , $A = 2$ , $B = 5$ , $M = 3$ , $S = 21$ (clan pattern 2,1,2,1,…).
Seed: $X_{0} = 0$ . Recurrence: $X_{i} = (X_{i - 1} \cdot 2 + 5) mod 2^{20}$ .

We are observing 4 nights:

Night 1. A werewolf is turned with initial strength $X_{1} = (X_{0} \cdot 2 + 5) mod 2^{20} = 5$ and joins clan 2. The median of ${5}$ is 5.
Night 2. A werewolf is turned with initial strength $X_{2} = (X_{1} \cdot 2 + 5) mod 2^{20} = 15$ and joins clan 1. The lower median of ${5, 15}$ is 5.
Night 3. A werewolf is turned with initial strength $X_{3} = (X_{2} \cdot 2 + 5) mod 2^{20} = 35$ and joins clan 2. Because it's blood moon, this werewolf and his clanmate gain 1 strength, and now have 36 and 6 strength, respectively. The median of ${6, 15, 36}$ is 15.
Night 4. A werewolf is turned with initial strength $X_{4} = (X_{3} \cdot 2 + 5) mod 2^{20} = 75$ and joins clan 1. (Note that strength increments from blood moons do not affect the generation of later $X_{i}$ values — the recurrence always uses the original $X_{i - 1}$ .) The lower median of ${6, 15, 36, 75}$ is 15.

The sum of medians recorded after these 4 nights is $5 + 5 + 15 + 15 = 40$ .

Case 2.

Parameters: $N = 5$ , $A = 131072$ , $B = 8$ , $M = 1$ , $S = 7$ (always clan 7).
Seed: $X_{0} = 0$ . Recurrence: $X_{i} = (X_{i - 1} \cdot 131072 + 8) mod 2^{20}$ with $2^{20} = 1, 048, 576$ .

The $X_{i}$ values of the first 5 werewolves are:

$X_{1} = X_{0} \cdot 131072 + 8 mod 2^{20} = 8$
$X_{2} = X_{1} \cdot 131072 + 8 mod 2^{20} = 8$
$X_{3} = X_{2} \cdot 131072 + 8 mod 2^{20} = 8$
$X_{4} = X_{3} \cdot 131072 + 8 mod 2^{20} = 8$
$X_{5} = X_{4} \cdot 131072 + 8 mod 2^{20} = 8$

Since $M = 1$ , every night is a blood moon, and because all werewolves are in clan 7, the entire set gains +1 after each joining:

Night 1: add $8$ , then +1 → ${9}$ ; median $= 9$ .
Night 2: add $8$ , then +1 to both → ${9, 10}$ ; lower median $= 9$ .
Night 3: add $8$ , then +1 to all three → ${9, 10, 11}$ ; median $= 10$ .
Night 4: add $8$ , then +1 to all four → ${9, 10, 11, 12}$ ; lower median $= 10$ .
Night 5: add $8$ , then +1 to all five → ${9, 10, 11, 12, 13}$ ; median $= 11$ .

Sum of medians: $9 + 9 + 10 + 10 + 11 = 49$ .