SENIOR 1

Culture

Input File: cultin.txt
Output File: cultout.txt
Time Limit: 1 second

You are a biologist working in a large laboratory. For the last month you have been growing a culture of your favourite bacteria, Bacillus Fortranicus. You are particularly interested in the way in which it grows in hostile environments.

Today is the last day of your experimentation. With anticipation you pull your log book from the shelf, but in your excitement you knock a bottle of acid from the bench. You watch in despair as it spills across your log book and your precious notes dissolve before your eyes.

You try desperately to recall some statistics. How many individual bacteria did you begin with? You can't even remember for how many days the experiment has been running. In desperation you call over your lab assistant.

"No, I don't remember how many bacteria we began with either," she says. "But I do remember that it was an odd number. Oh yes, and the number of bacteria doubled each day." She looks down at the bench, sniffs the acid and walks back to her desk with a wrinkled nose.

Although you have lost your notes, you can still count the total number of bacteria that you have now. Combining this total with the assistant's information, you must write a program to answer your two original questions. That is, you must calculate (i) how many bacteria you began with, and (ii) for how many days the experiment has been running.

Input

The input file will consist of one line only. This line will contain a single integer n representing the number of bacteria that you have now. You are guaranteed that 1 <= n <= 30,000.

Output

The output file must consist of the two integers b and d on a single line, where b represents the number of bacteria at the beginning of the experiment and d represents the number of days for which the experiment has been running. These two integers must be separated by a single space.

Sample Input

136

Sample Output

17 3

The sample data above can be explained as follows. We are given that the final bacteria count is 136. Observe that 136 = 17 x 2 x 2 x 2. Since 17 is odd, we see that the initial bacteria count was 17. Furthermore, the bacteria count has doubled three times and so the experiment must have been running for precisely three days.

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

Copyright © 2003 Australian Mathematics Trust