Coconuts: The Second Story

Time limit1sMemory limit128 MB

Summary

For each N, find the largest K such that K crew members can each remove one coconut, split the rest into K piles, and leave a final pile divisible by K.

Level: Medium5 of 10
Topics: Math, Number theory, Simulation, Brute force
Solved: No attempts yet

Problem

On October 9, 1926, a newspaper printed a short puzzle by the famous American playwright Ben Williams. It read as follows.

Five men were shipwrecked on a desert island. On the first day they worked together all day long and gathered a pile of coconuts.

That night the first man woke up and counted the coconuts. He found that if he set exactly one aside, the rest could be split into five equal piles. So he gave that one coconut to a monkey that happened to pass by, divided the remainder into five equal piles, secretly hid his own share, and went back to sleep.

Right afterwards the second man woke up and counted them, and again removing one coconut left an amount divisible into exactly five equal piles. He too gave one to the monkey, split the rest into five, hid his share, and went to sleep.

The third, the fourth, and the fifth man each did exactly the same thing in turn.

The next morning all five woke up and counted the coconuts that were left. This time the pile could be split into exactly five equal piles with none left over for the monkey, so they divided it into five and each took one pile.

How many coconuts had they gathered in the first place?

This puzzle actually has infinitely many answers, but the smallest of them is $3121$ .

That, however, is not the problem we are going to solve. Let us think about the coconut story in reverse.

Suppose they originally gathered $N$ coconuts, and that $K$ people managed to share out all of the coconuts by following the rules above. In other words:

each of the $1$ st through $K$ th people, on their own turn, can give one of the remaining coconuts to the monkey and then split what is left into exactly $K$ equal piles, taking one pile as their share, and
finally, in the morning, the remaining coconuts can be split into exactly $K$ equal piles with none left over for the monkey.

What is the largest possible value of $K$ ?

Input

The input consists of several test cases.

Each test case is a single line containing one integer $N$ . A line with $N = -1$ marks the end of the input and must not be processed.

Output

Print one line for each $N$ .

If a valid $K$ exists, then for the largest possible $K$ print N coconuts, max(K) people and 1 monkey, where N is replaced by the input value and max(K) by the maximum number of people.
If no $K$ can split the coconuts according to the rules, print N coconuts, no solution.

Constraints

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

Examples1

Example 1

Input

Expected output

25 coconuts, 3 people and 1 monkey
30 coconuts, no solution
3121 coconuts, 5 people and 1 monkey