Maximum Score
Tag(s):

## Algorithms, Hard

Problem
Editorial
Analytics

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

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

September Rush

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Game Theory
• Basic Programming > Implementation
• Algorithms > Dynamic Programming
• Algorithms > Sorting