All Tracks Basic Programming Recursion Recursion and Backtracking Problem

Divide Number
/

Algorithms, Depth First Search, String Manipulation

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?