ZOJ What day is that day? (觅最小周期)

ZOJ 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. 

#include<stdio.h>
#include<math.h>
int c[297];
void init()
{
    int a;
    c[0]=1;
    for(int i=1;i<=295;i++)
    {
        a=(i+1)%7;
        for(int j=2;j<=i+1;j++)
        a=(a*(i+1))%7;

        c[i]=(c[i-1]+a)%7;
    }
}
int main()
{init();
    int n,t;
    char day[8][20]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        n%=294;
        if(n)n--;
        else n=293;
        int d=c[n];
        if(d)d-=1;
        else d=6;
        printf("%s\n",day[d]);
    }
}