Description

In the network era, opportunities and crises coexist. After the "Y2K bug" was solved, would a new "bug" appear? The answer is yes: "the year 2038" is a new hurdle.

Maybe everyone already knows what the $2000$ year problem in computers is, but when did the $2038$ year problem emerge?

Programs written in C will not encounter the $2000$ year problem, but they will have the $2038$ year problem. This is because most C programs use a "standard time library," which stores time information in a standard $4$-byte, that is, $32$-bit, format.

When it was designed, this $4$-byte time format took $1970$ year $1$ month $1$ day at $0$ hour $0$ minute $0$ second as the time origin (value $0$). All subsequent times are counted by accumulating seconds from this point.

For example, if the accumulated value has reached $919642718$, it means that $919642718$ seconds have passed since $1970$ year $1$ month $1$ day at $0$ hour $0$ minute $0$ second. Converted, it should be Sunday, $1999$ year $2$ month $21$ day at $16$ hour $18$ minute $38$ second.

The advantage of calculating time this way is that by subtracting any two time values, you can quickly get the number of seconds between them, and then use other routines to convert it into a human-readable year-month-day hour-minute-second format.

The maximum value of a $4$-byte, that is, $32$-bit, storage is $2147483647$. Note! The key to the $2038$ year problem lies here—after time ticks through the heart-stopping final second $2147483647$, it will overflow into a negative number, meaning the time becomes invalid. The exact moment is Tuesday, $2038$ year $1$ month $19$ day at $03:14:07$. After that, all C programs using this "standard time library" will run into trouble with time calculations.

Your task: given a computer whose time variable has length $N$ bits and a given "time origin," determine the last valid time with respect to this "time origin."

Input Format

The first line contains the number of test cases $T$.

Lines $2$ to $T+1$: each line contains $7$ integers describing one test case: the number of bits of the time variable (in binary), followed by the year, month, day, hour, minute, and second of the "time origin."

Output Format

Output $T$ lines. For each test case, output $1$ line with $6$ integers: the year, month, day, hour, minute, and second of the last valid time.

1                             
16 2000 1 1 0 0 0

2000 1 1 9 6 7

2
32 1970 1 1 0 0 0
32 2015 11 8 8 30 0

2038 1 19 3 14 7
2083 11 26 11 44 7

Hint

For $50\%$ of the testdata, the number of bits of the variable $\le 16$.

For all testdata, the variable length $\le 32$, the number of test cases $\le 1000$, and $0 \le$ year $\le 10000$.

Translated by ChatGPT 5