# Day of the Week

#### Write a function that calculates the corresponding day of the week for any particular date in the past or future.

#### For example, for the date 28th August 2020 happens to be Friday. Hence the expected output will be Friday.

##### Input format :

```
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow:
The first line of each test case or query contains the three space-separated integers denoting the 'Day', 'Month', and the 'Year' respectively.
```

##### Note :

```
It's guaranteed that the input date will always be a valid one.
```

##### Output format :

```
For each test case/query, print a single line containing a single string denoting the corresponding day of the week for the particular input date.
The answer will be one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.
The output for every test case will be printed in a separate line.
```

##### Note :

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 10 ^ 5
1 <= Day <= 31
1 <= Month <= 12
1 <= Year <= 2,000,000
Time Limit : 1 sec.
```

Resources - https://en.wikipedia.org/wiki/Determination_of_the_day_of_the_week

There are multiple ways and complicated algorithms to solve this problem like Tomohiko Sakamoto’s Algorithm and Zeller Formula. You can look for them over the web, but we will go with a more intuitive solution.

If we know today is Sunday then we can easily tell that after 2 days it will be Tuesday or after 10 days it will be Wednesday.

Similarly, we know according to the Gregorian calendar (the calendar we follow) that it’s Monday on 1st Jan 1 AD. So, if we can count the number of days passed till current day then we can easily find the Day of the Week for the current day.

To make our calculations easier we can first skip leap days and calculate the number of days passed. Then we can add the leap days separately.

Also, we can precalculate and keep some constant values like:

- Array Storing Names of Days in the correct order of Modulo 7.

DaysName[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

- Number of Days Passed till Month 0,1,2....11 ignoring leap years.

noOfDaysPassedTillMonth[] = {0,31,59,90,120,151,181,212,243,273,304,334}

So ignoring leap days, totalNoOfDaysPassed = 365*(year - 1) + noOfDaysPassedTillMonth[month-1] + days.

Now for leap days, we need to count the number of leap years passed till current year also we need to ignore the current year if leap day i.e. 29th February is not passed in the current year.

Pseudocode:

if(month<=2)

year--

Then, we can calculate the number of leap years by counting the number of multiples of 4 excluding the number of multiples of 100 and finally including the number of multiples of 400.

Pseudocode:

leapDays = (year/4) - (year/100) + (year/400);

totalNoOfDaysPassed += leapDays;

return DaysName[totalNoOfDaysPassed % 7]