gNumbers

구글 직원은 수를 좋아하고, 수를 소재로 한 게임은 더 좋아한다. 직원 Laurence와 Seymour는 gNumber를 소재로 한 2인용 게임을 만들었다. 어떤 수의 각 자리 숫자를 모두 더한 값에 1과 자기 자신 말고 다른 양의 약수가 없으면, 그 수를 gNumber라고 부른다. 이 정의에 따라 1도 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가 이긴다.