Let us denote by d(n) the sum of all divisors of the number n, i.e. d(n) = ∑_{k | n} k.

For example, d(1) = 1, d(4) = 1+2+4=7, d(6) = 1+2+3+6=12.

For a given number c, find the minimum n such that d(n) = c.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

Each test case is characterized by one integer c (1 ≤ c ≤ 10^7).

Output

For each test case, output: 

  * "-1" if there is no such n that d(n) = c; 
  * n, otherwise. 

Example

Input


12
1
2
3
4
5
6
7
8
9
10
39
691


Output


1
-1
2
3
-1
5
4
7
-1
-1
18
-1

import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class ShortTask implements Closeable {

  private final InputReader in = new InputReader(System.in);
  private final PrintWriter out = new PrintWriter(System.out);

  public void solve() {
    preprocess();
    int t = in.ni();
    while (t-- > 0) {
      int x = in.ni();
      int result = map[x];
      out.println(result == 0 ? -1 : result);
    }
  }

  private final int MAX_N = (int) 1e7;
  private int[] map = new int[MAX_N + 1];

  private void preprocess() {
    int[] sieve = new int[MAX_N + 1];
    sieve[1] = 1;
    map[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
      if (sieve[i] == 0) {
        for (long j = 1L * i * i; j <= MAX_N; j += i) {
          int idx = (int) j;
          sieve[idx] += i;
          if (idx != i * i) {
            sieve[idx] += j / i;
          }
        }
      }
      sieve[i] += (i + 1);
      if (sieve[i] <= MAX_N && map[sieve[i]] == 0) {
        map[sieve[i]] = i;
      }
    }
  }

  @Override
  public void close() throws IOException {
    in.close();
    out.close();
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int ni() {
      return Integer.parseInt(next());
    }

    public long nl() {
      return Long.parseLong(next());
    }

    public void close() throws IOException {
      reader.close();
    }
  }

  public static void main(String[] args) throws IOException {
    try (ShortTask instance = new ShortTask()) {
      instance.solve();
    }
  }
}
