Problem Description

Xiao Lan discovered a magic alarm clock. Starting from the Unix epoch time ($1970$-01-01 $00:00:00$), every $x$ minutes the alarm clock will ring once (it also rings at the epoch time). This caught Xiao Lan’s interest, and he wants to study this alarm clock carefully.

For any given time in the format yyyy-MM-dd HH:mm:ss, Xiao Lan wants to know: before this time point (including this time point), what is the most recent alarm time?

Note that you do not need to consider time zones.

Input Format

The first line contains an integer $T$, indicating that the input contains $T$ test cases.

Next, $T$ test cases are given.

Each test case is on one line, containing a time (in the format yyyy-MM-dd HH:mm:ss) and an integer $x$, where $x$ is the alarm interval (in minutes).

Output Format

Output $T$ lines. Each line contains a time (in the format yyyy-MM-dd HH:mm:ss), which is the answer for each test case in order.

2
2016-09-07 18:24:33 10
2037-01-05 01:40:43 30

2016-09-07 18:20:00
2037-01-05 01:30:00

Hint

For all test cases, $1 \le T \le 10$ and $1 \le x \le 1000$. All given time formats are guaranteed to be valid.

Translated by ChatGPT 5