You have given a code snippet -

int k = 0;
int gcd (int a, int b) {
   if (b == 0)
       return a;
   else{
       ++k;
       return gcd (b, a % b);
    }
}

Find the minimum possible non-negative integers of \(a\) and \(b\) such that \(a > b\) and this code snippet outputs given \(k\) value.

INPUT FORMAT

• The first line of the input contains a single integer \(T\) denoting the number of test cases.

• Each test case consists of an integer \(k\).

OUTPUT FORMAT

Print two integers \(a\) and \(b\) separated by space such that \(a > b\).

CONSTRAINTS

\(1 \leq T \leq 10\)

\(1 \leq k \leq 50\)