Mr. Macintosh is a landlord of the twentieth century. He has many
lands. The most interesting part is that the shapes of all these lands are like
right-angled triangles and the smaller two sides are of integer length. Mr. Macintosh
is a very busy man as he has many other properties apart from the lands.
Everyday his employees buy new lands and Mr. Macintosh believes that one day he
will own all the lands of the Universe. In one fine morning, he wakes up from
sleep and discovers that he does not have proper records of the lands owned by
him. So he hires a person to give him report on all his lands. The report
contains only the square of the length of the largest sides his lands. That is if his
triangular lands has three sides a, b, c and b is
the largest among a, b, c then the report will contain
only b*b. But Mr. Macintosh does not believe this person, so he hires you
to judge whether that man is honest or a fraud.
Input
The input file contains several lines of inputs. Each line of the input file contains an unsigned integer N or a number of the form N! (Factorial N) (4<=N<=10000000). Each of these integers denotes square of the length of the longest side of one of his lands.
Output
For inputs of the form N, you need to print the line “He
might be honest.” if square-root of N can be the largest side of one of his land, otherwise print, “He is a liar.” These lines should be printed on a single line.
For inputs of the form N!, you need to do the same thing described above. Apart from that you also
need to print the prime numbers with which you need to divide N! to make it the square of a valid largest side of one of his lands. If number of such
primes is more than 50 you should print the smallest 50 such primes. These primes are all printed in a single line separated by
a single space. But of course you need not print the primes if N! is itself the square of a valid longest side.
A blank line separates output for each line
of input. The sample input/output will make everything clear.
Sample Input:
Sample Output:
Shahriar Manzoor