Counting Multiples by Divisor Count

Time limit1sMemory limit512 MB

Summary
Given N up to 10^18, count positive integers X that are multiples of N and have exactly N divisors, or report infinitely many.
Level

Hard9 of 10

Topics
Number theory, Combinatorics, Math, Backtracking
Solved
No attempts yet

Problem

You are given a positive integer N. Count how many positive integers X satisfy both conditions below.

  • X is a multiple of N.
  • The number of positive divisors of X is exactly N.

Input

The first line contains the number of test cases T. Each of the next T lines contains one positive integer N.

Output

For each test case, print the number of positive integers X that satisfy the conditions. If infinitely many such integers exist, print -1.

Constraints

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 10^18

Hint

In the first case, 12 and 18 satisfy the conditions. In the second case, 113^112 satisfies the conditions.

Examples1

  1. Example 1

    Input
    3
6
113
144
    Expected output
    2
1
-1