SP9975 FSEQ - No Stories Any More!

你是否曾渴望在比赛中直接得到一个明确的问题，而不是被冗长的故事困扰？这些从“约翰去旅行”开始，经过“啰里啰嗦”，最后以“请帮助约翰”结尾的故事真是让人厌烦。我们都知道并没有真正的约翰，为什么要浪费参赛者的时间呢？作为曾经的参赛者，我们深知这种感受，因此决定省去这些无聊的故事，直接给出问题。 给定序列定义为：**F(0) = 0, F(1) = 1**，以及 \[ \sum_{i=0}^{n} F(i) = F(n+2) - 1 \] 对于给定的整数 \( M \)，我们生成了另一个无限序列：**T(i) = F(i) % M**。经过分析，我们发现此序列是周期性的：在经过一定次数 **C** 迭代后，该序列会重复自身，其中 C 是序列 T 的周期长度。我们定义 **H(j)** 为从位置 **j** 开始的、最左边的严格递增子序列，保留 T 中元素的相对顺序。具体来说： 1. **H(0)** 是 **T(j)**，即 H 中的第一个元素。 2. **H(1)** 是 T(k1)，其中 T(k1) 是第一个大于 T(j) 的元素，且 j < k1。 3. **H(2)** 是 T(k2)，其中 T(k2) 是第一个大于 T(k1) 的元素，且 k1 < k2，依此类推。 例如，如果 \( M = 4 \)，那么 T = [**0 1 1 2 3 1** 0 1 1 2 3 1 0 1 1 2 …]。在这种情况下：H(0) = [0 1 2 3]，H(3) = [2 3]，H(5) = [1 2 3]。**Length(H(j))** 是该序列的长度，例如 **Length(H(5))** = 3。序列 T 的 **周期长度(C)** 为 6。 对于给定的 \( M \)，你需要计算其周期长度 C，然后求解以下总和： \[ \sum_{k=0}^{C-1} \text{Length}(H(k)) \]

输入的第一行包含一个整数 \( T \)，表示测试用例的数量。接下来的 \( T \) 行中，每行给出一个整数 \( M \)，表示相应测试用例中序列 T 的重复周期长度 C。

对于每个测试用例，按格式输出 **“Case K: summation”**，其中 K 是测试用例编号，summation 是上述计算出的总和。

\[ 1 \leq T \leq 10^3 \] \[ 1 \leq M \leq 10^5 \] **本翻译由 AI 自动生成**