Description

在一些没有安排其他工作的日子中，选择一个工作日安排会议。最好是星期三，其次是星期二、星期五、星期四，星期一。

Input

第一个整数表示后面有N组数据，每组数据起始为一个整数M，表示后面有M个候选日期。日期格式为“YYYY-MM-DD”。

Output

每组数据输出找到的符合条件的最早日子。

Sample

Input

2
5
2006-04-22
2006-04-28
2006-04-21
2006-04-09
2006-04-03
3
2006-05-17
2006-05-18
2006-05-22

Output

2006-04-21
2006-05-17