Gregor is learning about RSA cryptography, and although he doesn't understand how RSA works, he is now fascinated with prime numbers and factoring them.

Gregor's favorite prime number is P. Gregor wants to find two bases of P. Formally, Gregor is looking for two integers a and b which satisfy both of the following properties.

  * P mod a = P mod b, where x mod y denotes the remainder when x is divided by y, and 
  * 2 ≤ a < b ≤ P. 



Help Gregor find two bases of his favorite prime number!

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1000).

Each subsequent line contains the integer P (5 ≤ P ≤ {10}^9), with P guaranteed to be prime.

Output

Your output should consist of t lines. Each line should consist of two integers a and b (2 ≤ a < b ≤ P). If there are multiple possible solutions, print any.

Example

Input


2
17
5


Output


3 5
2 4

Note

The first query is P=17. a=3 and b=5 are valid bases in this case, because 17 mod 3 = 17 mod 5 = 2. There are other pairs which work as well.

In the second query, with P=5, the only solution is a=2 and b=4.
2
17
5
 1
55439
 5
5
7
11
13
19

2 16
2 4
 2 55438
 2 4
2 6
2 10
2 12
2 18

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007 //998244353
#define pb push_back
#define endd '\n'
#define inf 1000000000000000000
#define ll long long
#define mk make_pair
#define fi first
#define all(a) a.begin(),a.end()
#define test ll int t,o;cin>>o;for(t=1;t<=o;t++)
#define goog cout<<"Case #"<<t<<": "
#define print(arr,n) for(ll w=0;w<n;w++)cout<<arr[w]<<" ";cout<<'\n'
#define print_dou(arr,n,m) for(ll w=0;w<n;w++){ for(ll o=0;o<m;o++){cout<<arr[w][o]<<" "; }cout<<endd;}
#define display(w) loop(i,w.size())cout<<w[i]<<" ";cout<<'\n'
#define mem(b,q)  memset(b,q , sizeof(b))
#define se second
#define trace(x) cout<<#x<<": "<<x<<" "<<endl
#define trace2(x,y) cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x,y,z) cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a,b,c,d) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define loop(i,n) for( i=0;i<n;i++)
#define checkbit(n, b) ((n >> b) & 1)
#define setbits(x) __builtin_popcount(x)  // returns no of set bits in x
#define PRECISION std::cout.unsetf ( std::ios::fixed );std::cout.precision(9)
#define PI 3.14159265358979323846
#define scout(a,b) cout<<fixed<<setpresion(b)<<a<<endd;
using namespace std;
ll max(int a,ll b){ return max((ll)a,b);}
ll min(int a,ll b){ return min((ll)a,b);}
ll min(ll a,int b){ return min(a,(ll)b);}
ll max(ll a,int b){ return max(a,(ll)b);}
ll min3(ll a,ll b,ll c){return min(a,min(b,c));}
ll min4(ll a, ll b, ll c, ll d){return min(min(a,b),min(c,d));}
ll min5(ll a, ll b, ll c,ll d,ll e){return min(min(a,b),min(min(c,d),e));}
ll max3(ll a,ll b,ll c){return max(a,max(b,c));}
ll max4(ll a, ll b, ll c, ll d){return max(max(a,b),max(c,d));}
ll max5(ll a, ll b, ll c,ll d,ll e){return max(max(a,b),max(max(c,d),e));}
ll lcm(ll a, ll b)
{
    ll g=__gcd(a, b);
    return a/g*b;
}
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// use it as ordered_set <ll> arr;

/*

	NOTE :

	8 direction movement
	int dx[] = { -1, -1,  0, 1, 1, 1,  0, -1 };
	int dy[] = {  0, -1, -1, -1,  0, 1, 1, 1 };

	plus directions
	int dx[]={1, 0, -1 , 0 };
	ind dy[]={0, 1,  0,  -1};


	knight movement
	int dxK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
	int dyK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

	in range l-r (inclusive)
	no of elements which give remainder
	0 = r/3-(l-1)/3
	1 = (r+1)/3-l/3
	2 = (r+2)/3-(l+1)/3

 	in general -> (r+remainder)/k-(l-1+remainder)/k

  maxx=*max_element(a,a+n);
  m=(m-1+n)%n;     move anti-clockwise  beaware : if u use some x instead of one use m=(m-x+ (n/x+1)*n)%n
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

  find_by_order() and order_of_key(). The first returns an iterator to the k-th largest element (counting from zero), the second � the number of items in a set that are strictly smaller than our item

  in case of multiple query , if u pass an array as argument make sure u pass its copy oterwise , the original array will change

  	iterate over bits
 	while (bits)
	{
    	if (bits & 1)
		{
    			 // Current bit is set to 1
    	}
		else
		{
        		// Current bit is set to 0
   		}

   		 bits >>= 1;
	}


	iterate diagonally

	 j=n-1;
    for(i=2*n-2;i>=0;i--)
    {
        ll k=max(0,j);
        for(ll x=k;x<n && i-x>=0 ;x++)
        {
            ll y=i-x;
        }
        j--;

    }

*/
long long power(long long a,long long b){
    long long ans=1;
    while(b>0){
        if(b&1){ans=(ans*a)%mod;}
                a=(a*a)%mod;
                b>>=1;
        }
    return ans;

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    PRECISION;
   test
   {
       ll i,j,k,n,p;
       cin>>p;
       cout<<2<<" "<<(p-1)/2<<endd;

   }







    return 0;
}
