本文共 2975 字，大约阅读时间需要 9 分钟。

今天是训练的第六天，感觉这样强度的比赛，补题和写博客就很锻炼自己的能力，比以前每个周打一两场cf，然后第二天散漫的补题强多了，这样虽然强度有点大，但是这一个星期下来感觉对于出题速度还有跟以前有区别的，这样自己的思绪就一直在解题上，并没有什么散漫，相信这一个假期下来还是会有很大进步的，补一下今天没做完的题目

The only difference between easy and hard versions is the maximum value of n.

You are given a positive integer number n. You really love good numbers so you want to find the smallest good number greater than or equal to n.

The positive integer is called good if it can be represented as a sum of distinct powers of 3 (i.e. no duplicates of powers of 3 are allowed).

For example:

30 is a good number: 30=33+31,

1 is a good number: 1=30, 12 is a good number: 12=32+31, but 2 is not a good number: you can’t represent it as a sum of distinct powers of 3 (2=30+30), 19 is not a good number: you can’t represent it as a sum of distinct powers of 3 (for example, the representations 19=32+32+30=32+31+31+31+30 are invalid), 20 is also not a good number: you can’t represent it as a sum of distinct powers of 3 (for example, the representation 20=32+32+30+30 is invalid). Note, that there exist other representations of 19 and 20 as sums of powers of 3 but none of them consists of distinct powers of 3.

For the given positive integer n find such smallest m (n≤m) that m is a good number.

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1≤q≤500) — the number of queries. Then q queries follow.

The only line of the query contains one integer n (1≤n≤104).

Output

For each query, print such smallest integer m (where n≤m) that m is a good number.

Example

Input 7 1 2 6 13 14 3620 10000 Output 1 3 9 13 27 6561 19683 这是一道贪心的题目，说实话自己解上午真没做出来，这是之后看了题解才搞明白的，看大佬思路就是把它表示成三进制。假设把 n加上 k 能得到 p 。 如果 k不足以使 n的三进制表示中 2 所处的位置中的最高位发生进位，那么 p 是不符合要求的，因为那个 2还是在那里。于是我们可以模拟进位，把这一位以及低于他的位全部改成 0，将比这这一位高且相邻的位加以。由于这一位是 2所处位置的最高位，所以比它还高的位只可能是 0 和 1 ，加上 1 后是 1 和 2 。万一加上 1后又出现一个新的 2 的为怎么办呢？没关系，我们以这个数作为 n ，再来一遍，直到没有位置有 2 。

#include
   
    using namespace std;typedef long long int ll;const ll MAXN=2e5+51;ll test,tot,kk,ptr,res;ll num[MAXN];inline ll read(){       register ll num=0,neg=1;    register char ch=getchar();    while(!isdigit(ch)&&ch!='-')    {           ch=getchar();    }    if(ch=='-')    {           neg=-1;        ch=getchar();    }    while(isdigit(ch))    {           num=(num<<3)+(num<<1)+(ch-'0');        ch=getchar();    }    return num*neg;} inline void solve(){       kk=read();    memset(num,0,sizeof(num)),tot=0,res=0;    while(kk)    {           num[++tot]=kk%3,kk/=3;    }    for(register int i=tot;i;i--)    {           if(num[i]==2)        {               num[i]=0,ptr=i+1;            for(register int j=i-1;j;j--)            {                   num[j]=0;            }            while(num[ptr]==1)            {                   num[ptr++]=0;            }            num[ptr]=1,tot=max(tot,ptr);        }       }     for(register int i=tot;i;i--)    {           res=(res*3)+num[i];    }    printf("%lld\n",res);}int main(){       test=read();    for(register int i=0;i