Maximum Product Partition with Minimum Partition Count

Given a positive integer \(n\), partition it into a sum of positive integers (each at least 1) such that the product of these integers is maximized. In case there are multiple partitions that yield the same maximum product, choose the partition with the smallest number of parts. Formally, if \(n = a_1 + a_2 + \cdots + a_k\) with each \(a_i \ge 1\), you need to maximize \(\prod_{i=1}^{k} a_i\) and, among all partitions attaining this maximum, minimize \(k\).

Note: For example, for \(n=10\), one optimal partition is \(3+3+4\) with a product of \(36\) using 3 parts, and for \(n=5\), an optimal partition is \(2+3\) with a product of \(6\) using 2 parts.

inputFormat

The input is read from stdin and consists of multiple test cases. The first line contains an integer \(T\) representing the number of test cases. The following \(T\) lines each contain a single positive integer \(n\).

Example:

3
10
5
4

outputFormat

For each test case, output a single line to stdout containing two space-separated integers: the maximum product achieved by partitioning \(n\) and the minimum number of parts in an optimal partition.

Example Output:

36 3
6 2
4 1

## sample

2
10
5

36 3
6 2

</p>