In history books, dates are typically mentioned, but rarely does it mention which day of the week. For example, we all know that Neil Armstrong landed on the moon on July 20, 1969, but was that a Monday? Or perhaps a Friday? (It's actually a Sunday.)
To solve this kind of problem once and for all, you decided to create a program that when given a date, gives the day of the week.
The first line will contain the integer ~N~ ~(0 \le N \le 1000)~, the number of lines that follows.
Each subsequent line of input will contain a date ~d~ in ISO 8601 format (i.e.
yyyy-mm-dd). For simplicity, we consider all dates up to
1752-09-02 to be in the Julian calendar, and every date since
1752-09-14 to be in the Gregorian calendar, as it was the case in Canada (and also the US, the UK, and other places that were part of the British Empire then). Dates in the range (
1752-09-14) will not be considered valid input.
The year number will be padded to four digits, but may contain more digits if required. The year may be optionally prefixed by a
-, which represents negative year numbers. Note that year 0 means 1 BCE, year -1 means 2 BCE, etc. The year will be in the range ~[-10^9, 10^9]~.
For each input date, output the day of the week of date ~d~, i.e. one of
Sunday, on its own line.