问题3245--ZaakDov is doing his math problem!

3245: ZaakDov is doing his math problem!

[命题人 : ]
时间限制 : 4.000 sec  内存限制 : 64 MB

题目描述

Given an odd prime p. You are to tell whether p can be written into form a^2+b^2 (0

输入

There will be up to 2*10^5 test cases. An odd prime p (3<=p<2*10^9) in each line. End with EOF.

输出

For each number p, if p can be written into form a^2+b^2 (0<=b), output one line that contains "Legal a b", and if not just output one line that contains "Illegal". For a certain p that can be written into the form described above, any pair of a,b (0<=b) will do.

样例输入 Copy

3
5
7
11
13
17
19
23
29

样例输出 Copy

Illegal
Legal 1 2
Illegal
Illegal
Legal 2 3
Legal 1 4
Illegal
Illegal
Legal 2 5