IFK - Kalendar

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Pepe fascinujú magické datumy a vymyslela si hru, ktorej cieľom je zistiť, ktorý magický deň nastane najskôr. Obyčajný kalendár je ale veľmi mainstreamový, tak sa rozhodla používať medzinárodný fixný kalendár.
Ten bol vyvinutý ako alternatíva ku gregoriánskemu kalendáru. Jeho výhodou je, že konkrétny deň v roku vždy pripadá na ten istý deň týždňa, nevýhodou že kvôli tomu zavádza špeciálne dni mimo štandardného týždňa (ročný a priestupný). Rok má naďalej 365 alebo 366 dní, no tie sú rozdelené do 13 mesiacov po 28 dni (4 týždne). Výnimkou je 29. deň v decembri (29.13.) a prípadny priestupný deň 29.6.

Magický dátum je potom taký, ktorý je v jednom z tvarov (DDMMYY):

ABABAB
ABCCBA
ABCABC
ABABBA
BAABBA
ABBABA

Kde A,B,C su nejaké cifry (aj rovnaké).
Na prípadný rok 2100+ sa zatiaľ veľmi nemyslelo, počítajte s tým, že sa počet začne od 00

Úloha

Pre daný dátum nájdite najbližší magický dátum.

Vstup

V prvom riadku súboru sa nachádza číslo Q udávajúce počet sád.

Nasleduje Q riadkov so vstupným dátumom v tvare DDMMYY

1 ≤ Q ≤ 10 000
01 ≤ DD ≤ 28/29
01 ≤ MM ≤ 13
00 ≤ YY ≤ 99

Výstup

Výstupom programu je najbližší magický dátum pre každú sadu.

Príklad

Vstup:

Výstup:

100100
181181
111111

16 Domáce 1