Ovi, our beloved Senior brother. He has to do a lot of dateTime calculation in his busy life. He always wants to know the date after x days. He wants to give less effort to do this calculation. Can you make it easy for him?

Input

The first line contains one integer t (1 <= t <= 100) – the number of queries. The first line of each query contains a date in dd-mm-yyyy format, which is a valid date. The next line contains x (1 <= x <= 9999) number of days required to add with given date.

Output

Find out the corresponding date after x days. See the format in example.

Example

Input:

3
10-12-2020
12
29-02-2016
1010
03-12-2019
120

Output
22-12-2020
05-12-2018
01-04-2020