Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

DDATE2 - Dos Date (all languages available)

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.


Added by:Piotr Ką…kol
Date:2010-03-27
Time limit:4.954s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC SCM qobi VB.NET
Resource:Copy of A@K@$h J0h@rI's DDATE with all languages available

hide comments
2012-03-02 00:38:14 Hallvard Norheim Bø
Piotr: What's wrong with my Java solution?
It gives the same output as my AC Python solution both locally and on ideone.com :/

BTW, what's the range for years? And should day-of-month be zero padded if it's one digit?

Edit: found a way that works!

Last edit: 2012-03-02 11:08:20
2011-07-31 21:27:09 Hallvard Norheim Bø
Ok, I somehow believed a missing bash command would cause a RE, not WA.
2011-07-31 11:11:04 Piotr KÄ…kol
@hallvabo - It doesn't print the month:
line 5: date: command not found
2011-07-31 00:38:58 Hallvard Norheim Bø
My latest bash solutions gives correct answer for the example inputs, and runs fine on ideone.com. What's the issue?
2010-10-24 11:25:51 Piotr KÄ…kol
mktime from PHP is now available.

Last edit: 2010-10-24 11:26:27
2010-09-05 20:22:08 Piotr KÄ…kol
Now DDATE is available for all languages. You can submit there Your codes and gain more points.

Last edit: 2010-10-24 11:26:46
2010-08-04 20:17:47 Zoltán Zámbori
Yes, but too late. I found a shorter way :-)
2010-07-30 15:19:03 Piotr KÄ…kol
Langinfo is available
2010-04-01 23:09:08 Piotr KÄ…kol
Perhaps it is not available or You use it wrong.
Maybe that will help You:
perldoc.perl.org
On main SPOJ it also gets compile error.
2010-04-01 22:23:45 Zoltán Zámbori
I would like to send a short Perl solution, but: "Can't locate I18N/Langinfo.pm ..."
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.