1187 - SCU-G
Time Limit : 1 Second
Memory Limit : 128 MB
- A three tower of honoi contains 3*N disks of different sizes,
three of each size. (three of size 1, three of size 2, ... ,three of size N)
We are required to move only one disk at a time ,
without putting a larger one over a smaller one .
How many moves does it take to transfer a three tower from one
peg to another, if we are required to reproduce the original
top-to-bottom order of all the equal-size disks in the final
- The first line of the input is the number of test cases.
For each case there is only one line contains only one integer N.
- For each test case output the answer on a line:
how many moves does it takes mod 20080913.
- sample input
6 1 4 7 11 133 1000000000
- sample output
5 89 761 12281 2603941 13645968