Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Ambiguous Dates
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 243 Accepted: 62

Description

Background

More than 200 companies in more than 50 countries all over the world contribute towards the success of the Merck Group. You can imagine that every day Merck Group Headquarters at Darmstadt gets loads of mail from all over the world, the layout of all the letters following the customary style of their origin. In particular, the representation of a date is often ambiguous if you do not know in what order day, month, and year are given.

For example, if you read 01-02-03, you do not know if that represents the first of February 1903, or 2003, or if it is the third of February 1901, or 2001. It might even be the second of March 2001, or some other permutation of the three numbers. Instead of the hyphens, there could also be slashes, backslashes, dots, commas, or no delimiters at all.

Problem

You are hired to write a program that converts dates given in an unknown format to the format of the Adjusted Calender of Merck (ACM). The latter specifies the number of days relative to November 4, 2001, an important day in Merck's history.

Input

The first line contains the number of scenarios.

Every scenario contains a single date on a line by itself. A date consists of three parts: A day, a month, and a year given in any order, separated either by exactly two identical delimiters, or not separated by delimiters at all. Delimiters can be slashes '/', backslashes '\', hyphens '-', dots '.', or commas ','. The day and month are represented by a single digit, or by two digits, the first of which can be a leading zero. Valid years are in the range 1700 . . . 2299; either all four digits are given, or just the last two that specify the year relative to the century. In the latter case, a leading zero may be omitted.

Dates are considered illegal if no valid interpretation exists. More precisely, a date is illegal if no classification of the digits as day, month, and year results in a valid date in the range January 1, 1700, to December 31, 2299. However, you can be sure that all dates given contain 3 to 8 digits, and no other characters except for maybe the two delimiters.

Remember that February 29 is a valid date for leap-years only. A year is a leap-year if and only if either its number is divisible by four, but not by one hundred, or if its number is divisible by four hundred. So, in particular, 2000 is a leap-year, while 1700, 1800, 1900, 2100, or 2200 are not.

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1.

For every scenario, print all possible interpretations of the given date in the format of the Adjusted Calender of Merck (ACM), each interpretation in a single line, in ascending order and with duplicates removed. If no valid interpretation exists, print a line containing Illegal date instead.

Terminate the output for each scenario with a single blank line.

Sample Input

```3
1631/02/29
2001-11-03
010203```

Sample Output

```Scenario #1:
Illegal date

Scenario #2:
-238
-1

Scenario #3:
-109847
-109820
-109513
-109456
-109149
-109119
-73323
-73296
-72989
-72932
-72625
-72595
-36799
-36772
-36465
-36408
-36101
-36071
-274
-247
60
117
424
454
36250
36277
36584
36641
36948
36978
72774
72801
73108
73165
73472
73502```

Source

[Submit]   [Go Back]   [Status]   [Discuss]