Let represent the sum of elements in set of size . We shall call it a special sum set if for any two non-empty disjoint subsets, and , the following properties are true:
; that is, sums of subsets cannot be equal.
If contains more elements than then .
For this problem we shall assume that a given set contains strictly increasing elements and it already satisfies the second rule.
Surprisingly, out of the possible subset pairs that can be obtained from a set for which , only of these pairs need to be tested for equality (first rule). Similarly, when , only out of the subset pairs need to be tested.
For a given set size , how many subset pairs need to be tested for equality?
First line contains an integer denoting the number of test cases.
Each of the following lines contain one integer - the size of set.
For each of test cases print one line containing a single integer - the number of subset pairs that need to be tested for equality. As this number can be extremely large, output it modulo .