All Tracks Basic Programming Recursion Recursion and Backtracking Problem

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:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?