HZNUOJ

与小明一起写作业

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:98     AC:13     Score:99.16

Description

虽然是美好的周末,但小明还是有一堆作业需要完成,其中一道题目他想了很久却还是没有结果,聪明的你一定能帮助他完成任务。定义一个数$n$的价值为其每一位数的乘积,(如$1234$的价值为$1*2*3*4 = 24$),现在给定一个数n,问在1到n的范围内(包括$1$和$n$)的所有数中,价值最大会是多少。

Input

第一行输入一个 $T(1 \leq T \leq 100)$ ,表示测试数据组数

接下来T行,每行一个数$n(1 \leq n \leq 2*10^9)$


Output

对于每一个$n$输出最大的价值量。

Samples

input
3 390 7 1000000000
output
216 7 387420489

Author

CHEN, Zequn