#include <bits/stdc++.h>
using namespace std;
void addwedge(vector<pair<long long int, long long int>> adj[], long long int u,
              long long int v, long long int wt) {
  adj[u].push_back(make_pair(v, wt));
  adj[v].push_back(make_pair(u, wt));
}
void addedge(vector<long long int> adj[], long long int u, long long int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}
vector<long long int> shortestpath(
    vector<pair<long long int, long long int>> adj[], long long int V,
    long long int src) {
  priority_queue<pair<long long int, long long int>,
                 vector<pair<long long int, long long int>>,
                 greater<pair<long long int, long long int>>>
      pq;
  vector<long long int> dist(V, 9e+18);
  pq.push(make_pair(0, src));
  dist[src] = 0;
  while (!pq.empty()) {
    long long int u = pq.top().second;
    pq.pop();
    for (auto x : adj[u]) {
      long long int v = x.first;
      long long int weight = x.second;
      if (dist[v] > dist[u] + weight) {
        dist[v] = dist[u] + weight;
        pq.push(make_pair(dist[v], v));
      }
    }
  }
  return dist;
}
void buildsegment(long long int arr[], long long int tree[], long long int n) {
  for (long long int i = 0; i < n; i++) tree[n + i] = arr[i];
  for (long long int i = n - 1; i > 0; --i)
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void updatesegment(long long int p, long long int value, long long int tree[],
                   long long int n) {
  tree[p + n] = value;
  p = p + n;
  for (long long int i = p; i > 1; i >>= 1)
    tree[i >> 1] = tree[i] + tree[i ^ 1];
}
long long int querysegment(long long int l, long long int r,
                           long long int tree[], long long int n) {
  long long int res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res += tree[l++];
    if (r & 1) res += tree[--r];
  }
  return res;
}
long long int findpar(long long int numb, long long int par[]) {
  if (par[numb] == numb)
    return numb;
  else
    return par[numb] = findpar(par[numb], par);
}
void setpar(long long int u1, long long int v1, long long int par[]) {
  long long int s1 = findpar(v1, par);
  long long int s2 = findpar(u1, par);
  if (s1 < s2) {
    par[s2] = s1;
  } else {
    par[s1] = s2;
  }
}
long long int extended_GCD(long long int a, long long int b, long long int& x,
                           long long int& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod = 1000000007) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int power(long long int a, long long int b,
                    long long int m = 1000000007) {
  a %= m;
  long long int ans = 1;
  while (b > 0) {
    if (b & 1) ans = ans * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return ans;
}
vector<long long int> nge(long long int arr[], long long int n) {
  stack<long long int> s;
  vector<long long int> ans(n, -1);
  s.push(0);
  for (long long int i = 1; i < n; i++) {
    if (s.empty()) {
      s.push(i);
      continue;
    }
    while (s.empty() == false && arr[s.top()] < arr[i]) {
      ans[s.top()] = i;
      s.pop();
    }
    s.push(arr[i]);
  }
  return ans;
}
void swap(long long int& a, long long int& b) {
  long long int temp = a;
  a = b;
  b = temp;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t = 1, n;
  cin >> t;
  while (t--) {
    cin >> n;
    long long int ans =
        (long long int)ceil((long long int)pow(n, (long double)0.5));
    long long int k = 0;
    long long int ans1 = 0, ans2 = 0;
    for (long long int i = 1; i <= 50000; i++) {
      if (ans * ans > n) {
        long long int find = ans * ans - n;
        ans1 = ans;
        ans2 = (long long int)pow(find, (long double)0.5);
        if (ans2 * ans2 == find &&
            ans1 * ans1 - (long long int)((ans2)) * (ans2) == n) {
          long long int idi = (ans1 / ans2);
          if (ans1 / idi == ans2) {
            k = 1;
            break;
          }
        }
      }
      ans++;
    }
    if (k == 0)
      cout << -1 << "\n";
    else
      cout << ans1 << " " << ans1 / ans2 << "\n";
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

Let's denote a m-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size m × m of this matrix contains at least one zero. 

Consider the following problem:

You are given two integers n and m. You have to construct an m-free square matrix of size n × n such that the number of 1's in this matrix is maximum possible. Print the maximum possible number of 1's in such matrix.

You don't have to solve this problem. Instead, you have to construct a few tests for it.

You will be given t numbers x1, x2, ..., xt. For every <image>, find two integers ni and mi (ni ≥ mi) such that the answer for the aforementioned problem is exactly xi if we set n = ni and m = mi.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of tests you have to construct.

Then t lines follow, i-th line containing one integer xi (0 ≤ xi ≤ 109).

Note that in hacks you have to set t = 1.

Output

For each test you have to construct, output two positive numbers ni and mi (1 ≤ mi ≤ ni ≤ 109) such that the maximum number of 1's in a mi-free ni × ni matrix is exactly xi. If there are multiple solutions, you may output any of them; and if this is impossible to construct a test, output a single integer  - 1. 

Example

Input

3
21
0
1


Output

5 2
1 1
-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void addwedge(vector<pair<long long int, long long int>> adj[], long long int u,
              long long int v, long long int wt) {
  adj[u].push_back(make_pair(v, wt));
  adj[v].push_back(make_pair(u, wt));
}
void addedge(vector<long long int> adj[], long long int u, long long int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}
vector<long long int> shortestpath(
    vector<pair<long long int, long long int>> adj[], long long int V,
    long long int src) {
  priority_queue<pair<long long int, long long int>,
                 vector<pair<long long int, long long int>>,
                 greater<pair<long long int, long long int>>>
      pq;
  vector<long long int> dist(V, 9e+18);
  pq.push(make_pair(0, src));
  dist[src] = 0;
  while (!pq.empty()) {
    long long int u = pq.top().second;
    pq.pop();
    for (auto x : adj[u]) {
      long long int v = x.first;
      long long int weight = x.second;
      if (dist[v] > dist[u] + weight) {
        dist[v] = dist[u] + weight;
        pq.push(make_pair(dist[v], v));
      }
    }
  }
  return dist;
}
void buildsegment(long long int arr[], long long int tree[], long long int n) {
  for (long long int i = 0; i < n; i++) tree[n + i] = arr[i];
  for (long long int i = n - 1; i > 0; --i)
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void updatesegment(long long int p, long long int value, long long int tree[],
                   long long int n) {
  tree[p + n] = value;
  p = p + n;
  for (long long int i = p; i > 1; i >>= 1)
    tree[i >> 1] = tree[i] + tree[i ^ 1];
}
long long int querysegment(long long int l, long long int r,
                           long long int tree[], long long int n) {
  long long int res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res += tree[l++];
    if (r & 1) res += tree[--r];
  }
  return res;
}
long long int findpar(long long int numb, long long int par[]) {
  if (par[numb] == numb)
    return numb;
  else
    return par[numb] = findpar(par[numb], par);
}
void setpar(long long int u1, long long int v1, long long int par[]) {
  long long int s1 = findpar(v1, par);
  long long int s2 = findpar(u1, par);
  if (s1 < s2) {
    par[s2] = s1;
  } else {
    par[s1] = s2;
  }
}
long long int extended_GCD(long long int a, long long int b, long long int& x,
                           long long int& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1;
  long long int gcd = extended_GCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long int modinv(long long int a, long long int mod = 1000000007) {
  long long int x, y;
  extended_GCD(a, mod, x, y);
  if (x < 0) x += mod;
  return x;
}
long long int power(long long int a, long long int b,
                    long long int m = 1000000007) {
  a %= m;
  long long int ans = 1;
  while (b > 0) {
    if (b & 1) ans = ans * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return ans;
}
vector<long long int> nge(long long int arr[], long long int n) {
  stack<long long int> s;
  vector<long long int> ans(n, -1);
  s.push(0);
  for (long long int i = 1; i < n; i++) {
    if (s.empty()) {
      s.push(i);
      continue;
    }
    while (s.empty() == false && arr[s.top()] < arr[i]) {
      ans[s.top()] = i;
      s.pop();
    }
    s.push(arr[i]);
  }
  return ans;
}
void swap(long long int& a, long long int& b) {
  long long int temp = a;
  a = b;
  b = temp;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t = 1, n;
  cin >> t;
  while (t--) {
    cin >> n;
    long long int ans =
        (long long int)ceil((long long int)pow(n, (long double)0.5));
    long long int k = 0;
    long long int ans1 = 0, ans2 = 0;
    for (long long int i = 1; i <= 50000; i++) {
      if (ans * ans > n) {
        long long int find = ans * ans - n;
        ans1 = ans;
        ans2 = (long long int)pow(find, (long double)0.5);
        if (ans2 * ans2 == find &&
            ans1 * ans1 - (long long int)((ans2)) * (ans2) == n) {
          long long int idi = (ans1 / ans2);
          if (ans1 / idi == ans2) {
            k = 1;
            break;
          }
        }
      }
      ans++;
    }
    if (k == 0)
      cout << -1 << "\n";
    else
      cout << ans1 << " " << ans1 / ans2 << "\n";
  }
  return 0;
}

```