TEASTER - Waiting for Easter

Given a date, calculate the number of days until next Easter according to canonical (western) rule using the Gregorian Calendar.

Input

First line of input is a positive integer t<100, the number of testcases. Each of the following t lines contains a single date (1600<year<2100). The example below shows the date format.

Output

For every date print the number of days until next Easter or 0 if it's an Easter date.

Example

Input:
3
18 April 2011
27 February 1954
7 July 1777

Output:
6
50
286

Added by:numerix
Date:2011-04-18
Time limit:2s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.