Vinoth's Birthday may have ended but the celebration is still continuing in MIT. Cakes have an indispensable part in Birthday Celebrations. So, students are ready to eat cakes. Vinoth is fond of cakes. But, he found that one of his cakes is crying and trying to escape.

As it is a female cake, Vinoth did not want it to WALK away, because, well,it is Vinoth. He asked the cake 'Where are you trying to escape?' . It replied 'To Prayatna OLPC' .He said 'I will ask you a question. Answer it correctly, and then WALK AWAY'. Given x, he asked the cake to find the values of a and b such that pow(a, b) + pow(b, a) =x. It seemed very easy. So, he added an extra condition that (a-b) must be maximized.

Note

    It is guaranteed that a and b always exist and they are integers.

    a,b <= x

Input

   The first line contains ite, the number of test cases.

   Then ite line follows, each containing the number x.

Output Print ite lines, each containing a b.

Input Constraints

  ite<=1000

  1=x<=100