회문 날짜
시간 제한1초메모리 제한512 MB
주어진 날짜마다 점을 무시하고 앞뒤가 같은, 즉 회문이 되는 다음 날짜를 윤년을 고려해 구한다.
문제
자그레브 대학교의 시험 기간이 끝났고, 학생들은 가장 좋아하는 일을 하고 있다. 바로 잠을 자는 것이다. 깨어 있는 드문 순간에 학생들은 보통 인스타그램 피드를 넘긴다. 파비얀도 그런 학생 중 하나다.
최근 그는 다음과 같은 글귀를 읽었다. 날짜 02.02.2020.은 지난 909년 동안 첫 번째 회문 날짜라는 내용이었다.
그는 이 글귀가 틀렸다는 것을 깨닫고 회문 날짜에 대해 궁금해져서, N개의 날짜 각각에 대해 그 날짜 다음에 오는 첫 번째 회문 날짜는 무엇인지 생각해 보았다. 날짜는 점을 무시했을 때 왼쪽에서 오른쪽으로 읽으나 오른쪽에서 왼쪽으로 읽으나 같으면 회문이라고 한다. 예를 들어 02.02.2020.과 12.10.0121.은 회문이고, 03.02.2020.과 12.07.1993.은 회문이 아니다.
참고: 이 문제에서는 2월이 29일까지 있는 윤년을 고려해야 한다. 이 문제에서 윤년은 4로 나누어떨어지는 해로 본다. 그 외의 경우 각 달은 순서대로 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31일이다.
입력
첫째 줄에는 문제 설명의 정수 N (1 ≤ N ≤ 10 000)이 주어진다.
다음 N개의 줄에는 DD.MM.YYYY. 형식의 유효한 날짜가 주어진다.
출력
입력으로 주어진 각 날짜에 대해, 그 날짜보다 엄격히 뒤에 오는 첫 번째 회문 날짜를 출력해야 한다. 그 날짜는 DD.MM.YYYY. 형식으로 출력하며, 답이 이 형식으로 존재함이 보장된다.