Divide Number
Tag(s):

## Algorithms, DFS, Medium, String

Problem
Editorial
Analytics

Given integer $N$, you need to find four integers $A,B,C,D$, such that they're all factors of $N$ ($A|N,B|N,C|N,D|N$), and $N=A+B+C+D$. Your goal is to maximize $A\times B\times C\times D$.

## Input format

First line contains an integer $T(1\le T\le 4\cdot 10^4)$, represents the number of test cases.

Each of the next $T$ lines contains an integer $N$ ($1\le N\le 4\cdot 10^4$, $N^4$ will not exceed 64 bit integer).

## Output format

$T$ lines, each line contains the answer ($A\times B\times C\times D$) to correspond test case. If there is no way to find such four numbers, output $-1$.

SAMPLE INPUT
1
8

SAMPLE OUTPUT
16

Explanation

$A=B=C=D=2$

Time Limit: 1.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), 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, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...
Your Rating:

## This Problem was Asked in Challenge Name

September Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Algorithms > Sorting
• Math > Convex Hull
• Algorithms > Dynamic Programming
• Data Structures > Trees
Notifications

?