UVA-524 - Prime Ring Problem

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 相同題目：ZOJ-d396

題意概要

題目給定一個由 $n$ 個點所組成的圓環 ($n$ 為偶數)，現在要將 $1$ 到 $n$ 的自然數分別填入這 $n$ 個點中，使得相鄰 $2$ 個點的數數字和是質數。下圖為 $n = 6$ 的情形。

• 分析：本題為「回溯法 (Backtracking)」的應用。由題目限制可以推出此題的最大總和不可能超過 $32$，因此可以先建立 $1$ 至 $32$ 的質數表，再由 回溯法 求解，唯獨要注意的是，因為題目給定的是一個「圓環」，所以可能答案的最後一個數值與第一個數值要加總進行質數判斷。

Input

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$ $D$. $M$ represents the month (from $1$ to $12$) and $D$ represents the day (from $1$ to $31$). The date will always be valid.

Output

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

Sample Input

8
1 6
2 28
4 5
5 26
8 1
11 1
12 25
12 31

Sample Output

Thursday
Monday
Tuesday
Thursday
Monday
Tuesday
Sunday
Saturday