Problem H. Pow

There are n numbers 3^0, 3^1, . . . , 3^n-1. Each time you can choose a subset of them (may be empty), and then add them up.
Count how many numbers can be represented in this way.

The first line of the input contains an integer T , denoting the number of test cases. In each test case, there is a single integers n in one line, as described above.
1 ≤ T ≤ 20, 0 ≤ n ≤ 1000

For each test case, output one line contains a single integer, denoting the answer.

4
9
7
8
233

512
128
256
13803492693581127574869511724554050904902217944340773110325048447598592

2018 Multi-University Training Contest 10