Cho một dãy số ~a_1~, ~a_2~, ..., ~a_{n}~ được sinh ngẫu nhiên như sau:

• ~a_1 = seed~
• ~a_{i} =(a_{i-1} \times mul + add)\%65536~

Với

Cho một số ~k \leq n~. Dãy đã cho có ~n-k+1~ dãy con độ dài ~k~. Hãy tính tổng tất cả các phần tử trung vị (phần tử nhỏ thứ ~\frac{k+1}{2}~) của ~n-k+1~ dãy con này).

Input

• Dòng đầu tiên chứa số test (không quá ~30~). Mỗi dòng tiếp theo chứa ~5~ số nguyên ~seed, mul, add, n, K~. (~0 \leq seed, mul, add \leq 65535~, ~1 \leq n \leq 250000~, ~1 \leq k \leq 5000, k \leq n~)

Output

• Với mỗi test in ra số hiệu test (theo mẫu) cùng với tổng các trung vị tìm được.

Sample Input

5
3 1 1 10 3
10 0 13 5 2
4123 2341 1231 7 3
47 5621 1 125000 1700
32321 46543 32552 17 17

Sample Output

Case #1: 60
Case #2: 49
Case #3: 102186
Case #4: 4040137193
Case #5: 25569

Note

• Với test 1, dãy sinh ra là ~3, 4, 5, 6, 7, 8, 9, 10, 11, 12~. Các dãy con là ~(3, 4, 5), \dots, (10, 11, 12)~. Các trung vị là ~4, 5, \dots, 11~.