Alice and Bob are playing a game. They both agree up on a number M and the score is set to 0 initially. Alice chooses t > 0 consecutive integers starting from 1 i.e numbers 1, 2, ...t. Bob chooses t consecutive integers starting from any x > 0 i.e numbers x, x + 1, x +2, ... x + t - 1. Alice and Bob both multiply all the numbers they have chosen. If the ratio of results got by Alice and Bob is 1:M they will increase the score by 1 and continue playing the game, else they quit playing the game. No two games played must be identical. Two games are said to be identical if both Alice and Bob chooses same sequence of numbers in both the games. Find the maximum score they can get for a given M.

Input
First line of the input is the number of test cases T. It is followed by T lines, each test case has a single number M.

Output
For each test case, print a single number, the maximum score they can get. If they can get infinite score, print -1.

Constraints
1 ≤ T ≤ 10
1 ≤ M ≤ 10^13

Read the editorial here

SAMPLE INPUT
5
14
7
10
3
2

SAMPLE OUTPUT
2
2
4
2
1

见题面

见题面