gNumber 게임 (큰 수)

어떤 수의 각 자리 숫자를 모두 더한 값이 1과 자기 자신 외에 양의 약수가 없으면, 그 수를 gNumber라고 한다. 1의 자릿수 합은 1이고 1은 1과 자기 자신 외에 약수가 없으므로, 1도 gNumber다.

Laurence와 Seymour가 gNumber로 게임을 한다. 먼저 게임에 참여하지 않는 사람이 시작 수 $N$을 정한다. 그다음 두 사람이 번갈아 차례를 진행한다.

차례가 된 사람은 현재 수 $C$가 gNumber인지 확인한다. gNumber라면 그 사람이 그 자리에서 진다. gNumber가 아니라면 $C$의 소인수 $P$를 하나 골라, $P$로 더 나누어떨어지지 않을 때까지 $C$를 $P$로 계속 나눈다. 예를 들어 현재 수가 72라면 2를 골라 9가 될 때까지 나누거나, 3을 골라 8이 될 때까지 나눌 수 있다. 나눈 결과가 새로운 현재 수가 되고, 상대의 차례로 넘어간다.

항상 Laurence가 먼저 시작한다. 두 사람 모두 최선의 수를 둘 때, 시작 수 $N$에 대해 누가 반드시 이기는지 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각 테스트 케이스의 시작 수 $N$이 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 이기는 사람의 이름으로 Laurence 또는 Seymour다.

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

$N = 2$일 때 자릿수 합은 2이고, 2는 1과 자기 자신 외에 약수가 없으므로 2는 gNumber다. 따라서 Laurence가 곧바로 지고 Seymour가 이긴다. $N = 3$도 같다.

$N = 4$일 때 자릿수 합은 4이고, 4는 1과 4 외에 2라는 약수가 있으므로 4는 gNumber가 아니다. 4의 소인수는 2뿐이라서 Laurence는 2를 골라 계속 나눌 수밖에 없고, 남는 수는 1이다. Seymour는 1로 차례를 시작하는데 1은 gNumber이므로 Seymour가 지고 Laurence가 이긴다.