Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1211.

Problem Description

Xiao A wants to split a positive integer $n$ into the sum of several positive integers, and maximize the product of the integers after splitting. Xiao A hopes you can help him compute the maximum possible product. Since the answer may be very large, you only need to output the result modulo $10^9$.

Formally, a split of $n$ is a set of positive integers $a_1,\dots,a_k$ such that $a_1+\cdots+a_k=n$, where $1\leq k\leq n$. You need to output, among all splits of $n$, the maximum value of $a_1\times \cdots\times a_k$ modulo $10^9$.

Input Format

The first line contains a positive integer $t$, the number of test cases.

For each test case: one line containing an integer $n$, the given positive integer.

Output Format

For each test case: output one line containing an integer, the maximum product after splitting $n$ modulo $10^9$.

3
5
8
100

6
18
755407364

Hint

For $40\%$ of the test cases, it is guaranteed that $n\leq 50$.

For all test cases, it is guaranteed that $1\leq t\leq 10^4$ and $1\leq n\leq 10^6$.

Translated by ChatGPT 5