Description
A pascal triangle is a triangle full of numbers in the following rule:
-
The left most number and right most number of each row is 1
-
For the rest of the numbers, they are the sum of the two numbers directly above it
The following is a picture of a pascal triangle with height = 5.
Given a pascal triangle with height h, please calculate the sum of all numbers in the pascal triangle.
Since the sum is very large, it is suggested to implement a Big Integer class to calculate the answer. For sample code of Big Integer class, please refer to hw4.
Hints and Reminders
-
Try to observe the sum of each row in the pascal triangle
-
Be careful of overflow while implementing big integer
-
Input
The first line contains a single integer T, meaning that there are T test case in one input.
Then there are T lines, each lines contains a single integer h, begin the height of pascal triangle.
-
1 <= T <= 100
-
1 <= h <= 100000
Output
For each test case, output sum of all numbers in the pascal triangle in a line.