For each even integer \(n\), list all pairs of primes \(p<q\) such that \(p+q=n\).

Input

The first line contains \(T\) followed by \(T\) even integers \(n\).

The input satisfies:

• \(1 \le T \le 20\)
• \(4 \le n \le 10^7\)
• \(n is even.\)

Output

For each query, print one pair per line as p q, in increasing order of \(p\).

Example

Input

1
6

Output