gNumber Game (Large)

A number is a gNumber if the sum of its digits has no positive divisor other than 1 and itself. The digit sum of 1 is 1, and 1 has no divisor other than 1 and itself, so 1 is a gNumber.

Laurence and Seymour play a game with gNumbers. Someone who is not playing first picks a starting number $N$. The two players then take turns.

On a turn, the player checks whether the current number $C$ is a gNumber. If it is, that player loses right there. Otherwise the player picks one prime factor $P$ of $C$ and divides $C$ by $P$ repeatedly until $P$ no longer divides it. For example, if the current number is 72, the player can pick 2 and divide down to 9, or pick 3 and divide down to 8. The result becomes the new current number and the turn passes to the opponent.

Laurence always moves first. Given the starting number $N$, report who is certain to win when both players play optimally.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains one starting number $N$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the winner's name, either Laurence or Seymour.

• $1 \le T \le 100$
• $1 < N \le 10^{15}$

For $N = 2$ the digit sum is 2, and 2 has no divisor other than 1 and itself, so 2 is a gNumber. Laurence loses immediately and Seymour wins. The same happens for $N = 3$.

For $N = 4$ the digit sum is 4, and 4 has the divisor 2 besides 1 and 4, so 4 is not a gNumber. The only prime factor of 4 is 2, so Laurence must pick 2 and divide until 1 is left. Seymour starts his turn on 1, which is a gNumber, so Seymour loses and Laurence wins.