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 ≤ M ≤ 105. NOTE: for any given test case, sequence T repeats after maximum C iterations where C ≤ 105.
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