Jerry is not good in studies, but he likes to solve puzzles and always challenges his friend Tom. Today Jerry challenged Tom to solve a new riddle. He says "You are given a Pascal's triangle of infinite height, and you are supposed to find the sum of all the integers present at the given height." As usual Tom is confused and turn to you for help.

Input

The first line of the input contains an integer T denoting the number of test cases.
Then T lines follow, where each line contains H, the height of Pascal's triangle.

Output

For given height of triangle for each test case you need to find the sum of all integers and output it modulo to 10^3.

Constraints

1 ≤ T ≤ 100
1 ≤ H ≤ 50

Example
Input:
3
1
5
10

Output:
1
16
512

见题面

见题面