以下の Q 個のクエリに答えてください。

• i 番目のクエリでは、整数 N_i が与えられる。
• 長さ M (M \geq 1) の整数列 A = {A_1, A_2, ..., A_M} において、そのポイントを A_1 \times A_2 \times ... \times A_{M-1} \times A_M とする。
• A_1 + A_2 + A_3 + ... + A_M = N_i かつ A_j\geq 0 を満たす整数列の中でのポイントの最大値を 10^{9}+7 で割ったあまりを出力する。

ただし、ポイントを 10^{9}+7 で割ったあまりの最大値ではなく、ポイントの最大値を 10^{9}+7 で割ったあまりを出力することに注意してください。

制約

• 入力は全て整数である。
• 1 \leq Q \leq 10^5
• 0 \leq N_i \leq 10^{18}

入力例1

2
3 4

出力例1

3 4

N_i = 3 の場合、例えば A = {3} という数列のポイントは 3 であり、これが最大です。

N_i = 4 の場合、例えば A = {2, 2} という数列のポイントは 2 \times 2 = 4 であり、これが最大です。