One day, Little Gyro saw Onlystar playing the Hanoi Tower and wanted to test him.
The ordinary Hanoi Tower is a game with three pillars A, B and C. Given a tower consisting of n discs, these discs are nested on the pillar A within a decreasing way of size to display. Our goal is to move the entire tower to another pillar C. Only one disc can be moved at a time, and the larger disc cannot be placed under the smaller disc during every movement. Here shows the picture of it:
Then Little Gyro modified the rule of the Hanoi Tower game, supposed that the relative position of three pillars A, B and C is from left to right. Onlystar was asked to move the entire tower consisting of n discs from the leftmost pillar A to the rightmost pillar C, However, he couldn't move any disc directly from pillar A to pillar C. It means that Onlystar can only move discs through the pillar B in the middle.
Now, given the total number of discs, Onlystar wants to know the minimum steps there may be.
输入描述:
There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤
), indicating the number of test cases. For each test case:
Each line contains one integer n (1 ≤ n ≤
), indicating the total number of discs.
输出描述:
For each test case, you should output the number of the minimum steps that Onlystar could achieve.
Because the number may be very large, just output the number mod
.