SP9975 FSEQ - No Stories Any More!

Have you ever wished to be given a direct problem statement in the contest? Do you hate the boring stories that problem setters write...starting from “john was going on a trip”…passing with “blablabla”…and ending with “kindly help John J”. We all know that there is no John so why wasting contestants time. As we were contestants and know that feeling very well, we decided to break that boring way and save your time… Given the following sequence details: **F(0) = 0, F(1) = 1** and **SUM F(i) \[i from 0 to n\] = F(n+2) - 1** For a given integer M, we will generate another infinite sequence defined as: **T(i) = F(i) % M**. We noticed that this is a repeating sequence: it repeats itself after some **C** iterations, where C is the cycle length for sequence T. Let’s define **H(j),** as the finite, _most left_, strictly increasing **sub**-sequence starting at position **j** in the sequence T, _preserving_ the elements order of T. In other words: 1\) **H(0),** the first element in H, is **T(j)** 2\) **H(1)** = T(k1), where T(k1) is the first element > T(j) where j < k1 3\) **H(2)** = T(k2), where T(k2) is the first element > T(k1) where k1 < k2, and so on For example, if M = 4, then T = \[**0 1 1 2 3 1** 0 1 1 2 3 1 0 1 1 2 …\]. Furthermore: H(0) = \[0 1 2 3\], H(3) = \[2 3\], and H(5) = \[1 2 3\]. **Length( H(j) )** is the number of elements in that sequence, e.g. **Length(H(5))** = 3. The **Cycle length(C)** for sequence T is 6. For a given M, you will calculate its C, and **evaluate** the following **summation**: **SUM Length( H(k) ) \[k = 0 to C-1\]** **Input Specification:** The first line of input contains an integer T that represents the number of test cases, then follow T lines each contains an integer 1 _given_ test case, sequence T repeats after maximum C iterations where C **Output Specification:** For each test case, output a single line of output in the form **“Case K: summation”** where K is the number of the test case and summation is as defined in the problem statement. **Sample input:** 1 4 **Sample Output:** Case 1: 16

N/A

N/A