Once upon a time there is an ancient kingdom, The emperor of the kingdom has a so strong mind to manage his land that he divide the kongdom to n(0<n<10^9) states! And he likes to go on a tour of inspection very much. He plans to travel everyday, and for each tour, he chooses a different combination of states to visit.

People in this kingdom, strangely enough, use the ternary system to count numbers, and the emperor prefer 1 to be the last digit of a number. So the number of states he choose would only be 3k+1 while k is an integer. Then, he would like to know how many combinations he can choose from to travel. As is known to all, emperors should study more of policy than maths and programming. So he turns to you, the most excellent mathematician and programmer, to give him the answer.

First line contain an integer t(t<=100), which means t cases follow.
Then comes t lines, each contains an integer n, which means the emperor has divided the kingdom to n states.

提交代码