코코넛, 두 번째 이야기

1926년 10월 9일자 신문에 미국의 유명 극작가 벤 윌리엄스가 낸 짤막한 문제 하나가 실렸다. 내용은 다음과 같다.

다섯 명의 남자가 무인도에 표류했다. 그들은 첫날 하루 종일 힘을 합쳐 코코넛을 모았다.

그날 밤 첫 번째 사람이 깨어나 코코넛을 세어 보니, 하나를 빼면 정확히 다섯 등분으로 나눌 수 있었다. 그래서 그는 지나가던 원숭이에게 코코넛 하나를 주고, 남은 것을 다섯 등분한 뒤 자기 몫 한 무더기를 몰래 숨기고 다시 잠들었다.

곧이어 두 번째 사람도 깨어나 세어 보니 하나를 빼면 정확히 다섯 등분이 되었고, 똑같이 원숭이에게 하나를 준 뒤 나머지를 다섯 등분하여 자기 몫을 숨기고 잠들었다.

세 번째, 네 번째, 다섯 번째 사람도 차례로 똑같이 행동했다.

다음 날 아침, 다섯 명이 모두 깨어나 남은 코코넛을 세어 보니 이번에는 원숭이에게 줄 필요도 없이 정확히 다섯 등분으로 나눌 수 있었다. 그래서 그들은 남은 것을 다섯 등분하여 한 무더기씩 나누어 가졌다.

그렇다면 그들이 처음에 모은 코코넛은 모두 몇 개였을까?

이 문제의 답은 사실 무수히 많지만, 그중 가장 작은 수는 $3121$개이다.

하지만 우리가 풀 문제는 이것이 아니다. 이 이야기를 거꾸로 뒤집어 생각해 보자.

처음 모은 코코넛이 $N$개였고, 위와 같은 규칙에 따라 $K$명이 코코넛을 모두 나누어 가지는 데 성공했다고 하자. 즉,

• $1$번째부터 $K$번째 사람까지 차례대로, 자기 차례에 남아 있는 코코넛에서 하나를 원숭이에게 주고 남은 것을 정확히 $K$등분하여 자기 몫 한 무더기를 가져갈 수 있어야 하고,
• 마지막으로 아침에 남은 코코넛을 원숭이에게 줄 필요 없이 정확히 $K$등분할 수 있어야 한다.

이때 $K$는 최대 몇이 될 수 있을까?

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스는 한 줄에 정수 $N$이 주어진다. $N = -1$인 줄은 입력의 끝을 의미하며, 이 줄은 처리하지 않는다.

각 $N$마다 한 줄씩 출력한다.

• 조건을 만족하는 $K$가 존재하면, 가능한 가장 큰 $K$에 대하여 N coconuts, max(K) people and 1 monkey 형식으로 출력한다. 이때 N은 입력값으로, max(K)는 가능한 최대 인원수로 바꾸어 쓴다.
• 어떤 $K$로도 규칙대로 나눌 수 없으면 N coconuts, no solution을 출력한다.

• $1 \le N \le 1{,}000{,}000$