Yet Another Hanoi Problem
题号:NC205341
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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 .
示例1

输入

复制
3
1
2
3

输出

复制
2
8
26