Programmeren 2011-2012

Draw up a monthly calendar for a given month in a given year. It is not allowed to use modules from The Python Standard Library.
monthly calendar

The first line of the calendar is the English name of the month (written in lowercase letters), followed by a space and the year. The entire text should be centered and written over about 20 positions. The next line contains the consecutive weekdays, each shortened to two small letters, starting with Sunday and separated by spaces. Then follow all dates of the month on different lines, neatly aligned with the correct day on which these dates fall. The days are always right aligned and written over two positions, with a space between the different days as it was also used for the weekdays in the header. The output of the calendar contains no blank lines, and there are never spaces at the end of a line.

For a given day $d$, month $m$ and year $j$ it can be calculated which weekday it is in the following way:
\[
\begin{array}{rcl}
j_0 & = & j - \frac{(14 - m)}{12} \\
x  & = & j_0 + \frac{j_0}{4} - \frac{j_0}{100} + \frac{j_0}{400} \\
m_0 & = & m + 12 \left(\frac{14 - m}{12}\right) - 2 \\
d_0 & = & (d + x + \frac{31m_0}{12})\!\!\!\mod 7
\end{array}
\] All fractions represent divisions (quotient) and mod is the modulo operator (remainder after integer division). Ultimately, the value $d_0$ is the weekday, in which case the value 0 stands for Sunday, 1 for Monday, 2 for Tuesday, and so on.

When drawing up the calendar, remember that February has a different number of days, depending on whether the specified year is a leap year or not

Input

The first line of the input contains an integer $t$ that indicates how many test cases there are. The next $t$ lines each contain two integers $m$ and $j$, which are separated by a single space. These respectively represent the month $m$ and the year $j$ for which a calendar needs to be issued.
output

Output

For each test case a calendar must be drawn up for the month $m$ and the year $j$. A blank line should always be present between two consecutive calendars.

Example

Input:

3
2 2012
3 2012
2 2013

Output:

   february 2012
Su Mo Tu We Th Fr Sa
          1  2  3  4
 5  6  7  8  9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29

     march 2012
Su Mo Tu We Th Fr Sa
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

   february 2013
Su Mo Tu We Th Fr Sa
                1  2
 3  4  5  6  7  8  9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28

Stel een maandkalender op voor een gegeven maand in een gegeven jaar. Hierbij is het niet toegelaten om gebruik te maken van modules uit The Python Standard Library.

De eerste regel van de kalender moet de nederlandstalige naam van de maand (uitgeschreven in kleine letters) bevatten, gevolgd door een spatie en het jaartal, waarbij de volledige tekst gecentreerd wordt uitgeschreven over 20 posities. De volgende regel bevat de opeenvolgende weekdagen, telkens afgekort tot twee kleine letters, startend met zondag en gescheiden door spaties. Daarna volgen op verschillende regels alle dagen van de maand, netjes uitgelijnd onder de juiste weekdag waarop deze dagen vallen. De dagen worden telkens rechts uitgelijnd over twee posities uitgeschreven, met een spatie tussen de verschillende dagen zoals dat ook voor de weekdagen in de hoofding gebruikt werd. De uitvoer van de kalender bevat geen lege regels, en er staan nooit spaties op het einde van een regel.

Voor een gegeven dag $d$, maand $m$ en jaar $j$ kan op de volgende manier berekend worden op welke weekdag deze dag valt.
\[
\begin{array}{rcl}
j_0 & = & j - \frac{(14 - m)}{12} \\
x   & = & j_0 + \frac{j_0}{4} - \frac{j_0}{100} + \frac{j_0}{400} \\
m_0 & = & m + 12 \left(\frac{14 - m}{12}\right) - 2 \\
d_0 & = & (d + x + \frac{31m_0}{12})\!\!\!\mod 7
\end{array}
\] Hierbij stellen alle breuken gehele delingen voor (quotiënt) en staat mod voor de modulo operator (rest na gehele deling). Uiteindelijk geeft de waarde $d_0$ de weekdag aan, waarbij de waarde 0 staat voor zondag, 1 voor maandag, 2 voor dinsdag, enzoverder.

Hou er bij het uitschrijven van de kalender ook rekening mee dat de maand februari een verschillend aantal dagen telt, afhankelijk van het feit of het opgegeven jaar een schrikkeljaar is of niet.

Invoer

De eerste regel van de invoer bevat een natuurlijk getal $t$ dat aangeeft hoeveel testgevallen er zijn. De volgende $t$ regels bevatten telkens twee natuurlijke getallen $m$ en $j$ die van elkaar worden gescheiden door één enkele spatie. Deze geven respectievelijk de maand $m$ en het jaartal $j$ aan waarvoor een kalender moet uitgeschreven worden.

Uitvoer

Voor elk testgeval moet de kalender voor de maand $m$ en het jaar $j$ uitgeschreven worden. Tussen twee opeenvolgende kalenders moet telkens een lege regel uitgeschreven worden.

Voorbeeld

Invoer:

3
2 2012
3 2012
2 2013

Uitvoer:

   februari 2012
zo ma di wo do vr za
          1  2  3  4
 5  6  7  8  9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29

     maart 2012
zo ma di wo do vr za
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

   februari 2013
zo ma di wo do vr za
                1  2
 3  4  5  6  7  8  9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28