동전

자하크는 지암시드의 적으로, 지암시드의 딸 아르나바즈와 샤흐른아즈를 붙잡았다. 그러나 그는 두 자매에게 퍼즐을 풀어 스스로 풀려날 기회를 주기로 했다.

자하크는 그림과 같이 0번부터 63번까지 번호가 매겨진 $8 \times 8$ 체스판을 가지고 있다. 64개의 칸에는 각각 동전이 하나씩 놓여 있다. 번호가 $c$인 칸의 동전은 다른 동전과 겉모양이 같지만 저주받은 동전이다. 각 동전은 앞면 또는 뒷면이 위를 향하고 있다.

자하크는 자매를 저녁 식사에 초대해 퍼즐을 설명한다. 식사가 끝나면 자매는 서로 다른 방으로 간다. 자하크는 아르나바즈의 방에 가서 체스판을 보여 주고 저주받은 동전의 번호 $c$를 알려 준다. 아르나바즈는 동전의 위치를 바꿀 수는 없지만, 동전을 최소 1개에서 최대 $k$개까지 뒤집을 수 있다. 같은 동전을 여러 번 뒤집어도 된다. 이후 자하크는 샤흐른아즈의 방으로 가서 체스판을 보여 준다. 샤흐른아즈가 저주받은 동전을 찾으면 두 자매 모두 풀려난다. 자매는 식사 중에 전략을 정할 수 있지만, 그 뒤로는 서로 연락할 수 없다.

자매가 이 퍼즐을 풀 수 있도록 도와라.

• $1 \leq T \leq 1000$,
• $0 \leq c \leq 63$.