# DSLCS 2011 Number Theory. Favorites

# Be Efficient

Consider an integer sequence consisting of **n** elements, where

**x _{0}** =

**a**,

**x _{i}** = ((

**x**

_{i}_{-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

**x _{0}** =

**2**,

**x _{i}** = (

**x**

_{i}_{-1}+

**2**) %

**4**+

**1**,

**i = 1, 2, 3, 4**

So, **x _{0}** =

**2**,

**x**=

_{1}**1**,

**x**=

_{2}**4**and

**x**=

_{3}**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.

2 2 1 2 4 4 923 278 195 8685 793

Case 1: 2 Case 2: 34