Shortening codes

In DOS, current date is stored in encoded form to reduce the space. Date is encoded in a single integer number. The binary form of the number can be divided to decode the date parameters.

Date is a sequence of 23 bits. First 14-bits for year, next 4-bits for month and finally 5 bits for day.

e.g., 12 February 1990 can be encoded as -

1990 02 12 ---> (11111000110 0010 01100) Binary Form
                ---> (1018956) Decimal Form

Your task is simple. You only will have to decode date from the given decimal encoded form.

Input

The input consists of N cases (0<N<1001). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with one positive integer X. This integer X is the encoded form which is to be decoded. 

X will fit in Integer(C Int) range.

Output

Output consist of exactly N lines of decoded form.

Example

Input:
5
1024275
1029012
1017036
903863
802507

Output:
19 August 2000
20 December 2009
12 June 1986
23 May 1765
11 June 1567

Author of this problem is A@K@$h J0h@rI.