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 10 12 98 99 4! 5! 6! 120! Sample Output He might be honest. He is a liar.

2/2 He might be honest. He is a liar. He is a liar. 3 He is a liar. 3 He might be honest. He is a liar. 7 23 31 67 71 79 83 103 107