Doomsday Algorithm

No. Doomsday algorithm is not a method to compute which day the world will end. It is an algorithm created by the mathematician John Horton Conway, to calculate which day of the week (Monday, Tuesday, etc.) corresponds to a certain date.

This algorithm is based on the idea of the doomsday, a certain day of the week upon which certain easy-to-remember dates fall. For example, 4/4 (the 4th of April), 6/6 (the 6th of June), 8/8 (the 8th of August), 10/10 (the 10th of October), and 12/12 (the 12th of December) are dates which always fall on doomsday. All years have their own doomsday.

In year 2012, doomsday is Wednesday. So all of 4/4, 6/6, 8/8, 10/10, and 12/12 are Wednesdays. Using that information, you can easily compute any other date. For example, the 13th of December, 2012 will be Thursday, the 14th of December, 2012 will be Friday, etc.

Other days which fall on doomsday are 3/7, 5/9, 7/11, 9/5, and 11/7. Also, in leap years, we have the following doomsdays: 1/11 (the 11th of January) and 2/22 (the 22nd of Febrary), and in non-leap years 1/10 and 2/21.

Given a date of year 2012, you have to compute which day of the week it occurs.

Input Specification

The input can contain different test cases. The first line of the input indicates the number of test cases.

For each test case, there is a line with two numbers: M and D. M represents the month (from 1 to 12) and D represents the day (from 1 to 31). The dates will always be valid.

Output Specification

For each test case, you have to output the day of the week upon which that date falls in 2012. The days of the week will be: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.

Sample Input

1. 8
2. 1 6
3. 2 28
4. 4 5
5. 5 26
6. 8 1
7. 11 1
8. 12 25
9. 12 31

download as text file

Output for Sample Input

1. Friday
2. Tuesday
3. Thursday
4. Saturday
5. Wednesday
6. Thursday
7. Tuesday
8. Monday

download as text file