DDATE - Dos Date

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 date.

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. Score is source length.

Input

The input consists of N cases (equal to about 1000). 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.  

1<=N<=1000

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



Added by:Aragorn
Date:2010-02-14
Time limit:1s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC GAWK MAWK BC C-CLANG NCSHARP CPP14-CLANG CLOJURE COBOL COFFEE D-CLANG D-DMD DART ELIXIR FSHARP FANTOM FORTH GO GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PYTHON3 PY_NBC R RACKET RUST CHICKEN SED SWIFT UNLAMBDA VB.NET
Resource:Own Problem from Code Combat(RGIIT Code Competition)

hide comments
2011-09-24 19:36:12 Abhinav Singh
what to do if x has more than 23 bits in binary form
2011-02-13 11:13:48 Piotr KÄ…kol
72 chars is not the best result.
The real champions are Shinichiro Hamaji and Jander who solved this problem in... 69 chars.

Last edit: 2011-06-11 19:14:03
2010-09-05 17:39:02 Mohammed Hafez
What about leading zeros!!!!
2010-09-05 17:39:02 Muntasir Azam Khan
Two suggestions:
1. Problem statement could be made clearer about input/output format. Do we print leading zeros for dates less than two digits or years less than four digits?

2. I don't understand what "You can try it in your languages. I will provide input output data" means. You don't have to provide anything else, just update your problem settings to allow other languages.
2010-09-05 17:39:02 Ruslan Sennov
@Ahmed Helal
I believe X=1 is incorrect input.
My program will output "1 0"

Last edit: 2010-02-22 15:54:08
2010-09-05 17:39:02 Ahmed Helal
Let me ask again as well: what should be the output of X=1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.