The Government of Byteland has decided to issue new currency notes with special protection features to commemorate their great mathematician Byteguru. Byteland has decided to issue notes using the following rules

1. It will issue notes upto value N such that all the sums from 1 to N should be possible through a selection of some of the notes from 1 to N.
2. The selection of the notes is to be done in way such that none of the selected note values can be made through a combination of two of the other selected notes.

For example, with N = 7,

The valid sets are: {1,1,1,1,1,1,1} {1,1,1,4} {1,2,2,2} {1,2,4}

Invalid sets are: a) {1,1,1,2,2} is invalid as one of the selected notes {2} can be made by combining two of the selected notes {1,1}. b) (1,1,1,1,3} is invalid as one of the selected notes {3} can be made as combination of three of the remaining selected notes {1,1,1} c) {1,1,3,6} is invalid beacuse the sum is not 7 (it is 11)

Before implementing this idea of issuing these new set of notes, the Government wants to know how many possible valid sets are there for a given N. Your program should help the Government to find this out.

Input

First line will contain the number of test cases T (1<=T<=6666). Each test case will have one line containing an integer N (<= 2^31-1).

Output

For each value of N, output the total number of valid sets on a separate line.