SP20970 HDEVIL - Alia and Handsome Devil

Alia 的数学老师给她布置了一份作业，要求她寻找「帅气」数。由于众所周知她非常「聪明」:P，因此她需要你的帮助。 老师对「帅气」数的定义是这样的：一个数被称为帅气数，当且仅当这个数所有真因数之和与 $m$ 取模的结果是一个恶魔数。恶魔数指的是其真因数个数是一个斐波那契数（如 0, 1, 1, 2, 3, 5...）。 注意：由于 Alia 的幸运数字是 1，她总是认为 1 是一个真因数 :P

第一行输入一个整数 $t$ 表示测试用例的数量，接下来每个测试用例占一行，每行包含两个整数 $n$ 和 $m$，分别代表要检查的数字和模数。

对于每个测试用例，输出一行，格式是 `Case #i : YES.` 如果该数是帅气数，否则输出 `Case #i : NO.`。请注意输出格式中的空格和句末的点。 ``` Case #i : YES. Case #j : NO. ```

- $t \leq 100$ - $2 \leq n \leq 10^9$ - $1 \leq m \leq 10^8$ **样例输入** ``` 2 6 5 100 45 ``` **样例输出** ``` Case #1 : YES. Case #2 : YES. ``` **解释** - **样例 1**：数字 6 的真因数是 1, 2, 3，它们的和为 6。模 5 后得到 1，数字 1 的真因数有 1 个，是一个斐波那契数。 - **样例 2**：数字 100 的真因数是 1, 2, 4, 5, 10, 20, 25, 50，它们的和为 117。模 45 后得到 27， 27 的真因数有 4 个，4 是一个斐波那契数。 **本翻译由 AI 自动生成**