Press to Unlock

A door lock has B buttons numbered from 1 through B, where 1 <= B <= 11. A password is entered by pressing one or more button combinations in a fixed order, then turning the handle.

A button combination is a nonempty set of buttons pressed at the same time. If a button is used in one combination, it cannot be used again in another combination of the same password. Some buttons may be left unused.

When B=8, (1-2-3)(4)(7-8) is a valid password made of the three combinations (1-2-3), (4), and (7-8) in that order. Buttons 5 and 6 are unused. In contrast, (1-2-3)(2-4)(5-6) is invalid because button 2 appears in two combinations.

Given the button count B for several door locks, compute how many distinct passwords can be made for each one.

The first line contains an integer N, the number of door locks. 1 <= N <= 100.

Each of the next N lines contains one integer B, the number of buttons on a door lock.

For each door lock, output the number of possible passwords on its own line, in input order.