11155 - Be Efficient

B Next Generation Contest 3 Time Limit: 2 seconds Be Efficient

一個整數序列有 N 個元素，其中

X₀ = A

X_i = (( (X_i-1) * B + C ) % M)+1       for i = 1 to N-1

假設給定 A, B, C, M, N 的值。

在 X 序列中，找有多少連續子序列總合是 M 的倍數。

例如當  A = 2, B = 1, C = 2, M = 4, N = 4
=> X₀ = 2, X₁ = 1, X₂ = 4 and X₃ = 3

連續子序列有 {2}, {2 1}, {2 1 4}, {2 1 4 3}, {1}, {1 4}, {1 4 3}, {4}, {4 3}, {3}. 

  

在這十個中，只有其中兩個 {1 4 3} 和 {4}是 4 個倍數。

 

Input

測資第一行會有一個整數 T (T < 500) 表示的測資組數。

對於每組測資會有 5 個整數 A, B, C, M, N。

(0 <= A, B, C <= 1000, 0 < M, N <= 10000)

Output

對於每組測資，輸出測資編號以及結果。 

Sample Input	Output for Sample Input
2 2 1 2 4 4 923 278 195 8685 793	Case 1: 2 Case 2: 34

Problem Setter: Mohiul Alam Prince
Moderator and Alternate Solution: Sohel Hafiz