B"Dhruvil and amenotiomoi are sitting in different countries and chatting online. Initially, amenotiomoi has an empty board of size n x n , and Dhruvil has a sequence of integers 1, 2, ldots, n^2 , each number occurring exactly once. The numbers may be placed in the cells of the board, each cell is either empty or contains exactly one number. The current state of the board is called good, if there is a way of placing the remaining numbers in empty cells so that all numbers except 1 have a neighbor with a smaller value. Two cells are neighbors if they share an edge. The rows are numbered from 1 to n from top to bottom, the columns are numbered from 1 to n from left to right. The cell at the intersection of the x -th row and the y -th column is denoted as (x, y) . To chat, amenotiomoi asks q queries to Dhruvil. Each time he provides Dhruvil with an empty cell (x, y) . Dhruvil has to place one of the remaining numbers in this cell so that the board is still good. Among all ways to do this, he chooses the largest possible number he can place and sends this number to amenotiomoi as the answer to the query. Since amenotiomoi knows the correct answer every time, he tells Dhruvil (x oplus k,y oplus k) instead of (x, y) , where k is the answer for the previous query. If amenotiomoi is sending the first query, he considers k = 0 . Each time Dhruvil has to decode the query and send the answer to amenotiomoi. Here oplus denotes the bitwise XOR operation. Help Dhruvil reply to all amenotiomoi's queries. Each test contains multiple test cases. The first line contains the number of test cases t ( 1 <= t <= 100 ). The description of the test cases follows. The first line of each test case contains two integers n and q ( 1 <= n <= 10^3 , 1 <= q <= n^2 ). The i -th of the following q lines contains two integers x_i' and $"...