write a go solution for Description:
This is the hard version of the problem. The only difference between the versions is the limit on the number of queries. In this version, you can make no more than 57 queries. You can make hacks only if both versions of the problem are solved.

This is an interactive problem!

salyg1n has given you a positive integer k and wants to play a game with you. He has chosen an array of n integers a_1,a_2,ldots,a_n (1<=a_i<=10^9). You must print a_1oplusa_2oplusldotsoplusa_n, where oplus denotes the bitwise XOR operation. You can make queries of the following type:

- ? i: in response to this query, you will receive a_ioplusa_i+1oplusldotsoplusa_i+k-1. Also, after this query, the subarray a_i,a_i+1,ldots,a_i+k-1 will be reversed, i.e., the chosen array a will become: a_1,a_2,ldotsa_i-1,a_i+k-1,a_i+k-2,ldots,a_i+1,a_i,a_i+k,ldots,a_n.

You can make no more than 57 queries to answer the problem.

Input Format:
The first line contains a single integer t (1<=t<=1000) – the number of test cases.

Output Format:
None

Note:
In the first test case, the jury has chosen the array a = [4,2,5,1]

In the second test case, the jury has chosen the array a = [5,7,1,3,3,7]. Output only the code with no comments, explanation, or additional text.