ZOJ3785：What day is that day?

It's Saturday today, what day is it after 1¹ + 2² + 3³ + ... + N^N days?

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is only one line containing one integer N (1 <= N <= 1000000000).

Output

For each test case, output one string indicating the day of week.

Sample Input

2
1
2

Sample Output

Sunday
Thursday

Hint

A week consists of Sunday, Monday, Tuesday, Wednesday, Thursday, Friday and Saturday.

通過打表發現周期是294，那麼就簡單了

#include 
#include 
#include 
using namespace std;

char day[10][10] = {"Saturday","Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
int s[300];

int work(int n)
{
    int sum = 1,i;
    for(i = 1;i<=n;i++)
    {
        sum = sum*n;
        sum%=7;
    }
    return sum;
}

int main()
{
    int t,n,i,j,len;
    s[0] = 0;
    for(i = 1;i<=294;i++)
    {
        s[i] = s[i-1]+work(i);
        s[i]%=7;
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        n%=294;
        printf("%s\n",day[s[n]]);
    }


    return 0;
}