Cho một số nguyên \(n\), chia nó thành tổng của \(k\) số nguyên dương, trong đó \(k \ge 2\) và tối đa hóa tích của các số nguyên đó.

Trả ra kết quả tối đa có thể nhận được.

Example 1:

• Input: n = 2
• Output: 1
• Giải thích: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

• Input: n = 10
• Output: 36
• Giải thích: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Input

• Dòng đầu tiên là số lượng bộ test \(n\)
• \(n\) dòng tiếp theo, mỗi dòng là một số nguyên

Output

• kết quả tối đa có thể nhận được tương ứng từng bộ test

Example

Sample input 1

2
2
10

Sample output 1

1
36