e-olymp
Competitions

DSLCS 2011 Number Theory. Favorites

Be Efficient

Consider an integer sequence consisting of n elements, where

x0 = a,

xi = ((xi-1 * b + c ) % m) + 1 for i = 1 to n - 1

You will be given the values of a, b, c, m and n. Find out the number of consecutive subsequences whose sum is a multiple of m.

Consider an example where a = 2, b = 1, c = 2, m = 4 and n = 4. Then

x0 = 2,

xi = (xi-1 + 2) % 4 + 1, i = 1, 2, 3, 4

So, x0 = 2, x1 = 1, x2 = 4 and x3 = 3. The consecutive subsequences are {2}, {2 1}, {2 1 4}, {2 1 4 3}, {1}, {1 4}, {1 4 3}, {4}, {4 3} and {3}. Of these 10 consecutive subsequences, only two of them adds up to a figure that is a multiple of 4: {1 4 3} and {4}.

Input

The first line of input is an integer t (t < 500) that indicates the number of test cases. Eact case consists of 5 integers a, b, c, m and n. a, b and c will be non-negative integers not greater than 1000. n and m will be a positive integers not greater than 10000.

Output

For each test case, output the case number followed by the result.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
2
2 1 2 4 4
923 278 195 8685 793
Output example #1
Case 1: 2
Case 2: 34