By Francisco Elio Parente Arcos Filho, UEA Brazil
In Nlogonia are made LED panels for christmas that work like fairy lights. Those panels are composed of N lamps placed horizontally side to side. And those panels have an especific behavior: soon as it is plugged, some lamps light up instantly . After that the lamp placed at the extreme left (the first one) switches between on and off after each flash. All the other lamps switch if the one placed at it's left turns off.
Vitor, a boy who lives in Nlogonia, has a big curiosity and wants to know if given the number of switches of the first lamp, what is the panel's final configuration.
The first line of the input contains a integer number N that especifies the quantity of test cases. Then the following N lines contains each one a P (1 ≤ |P| ≤ 60) string that represents the first configuration of the panel lamps. The lighted up lamps are represented by a character 'O' and the lighted off are represented by a 'X'. In the same line will have an integer number C (1 ≤ C ≤ 1018) that represents the amount of changes of the first lamp.
The outputs consists in one line per test case that has the final configuration after the first switches of the first lamp.
|Input Sample||Output Sample|