Problem: You are given a complete bipartite graph with 2n nodes, with n nodes on each side of the bipartition. Nodes 1 through n are on one side of the bipartition, and nodes n+1 to 2n are on the other side. You are also given an n × n matrix a describing the edge weights. a_{ij} denotes the weight of the edge between nodes i and j+n. Each edge has a distinct weight.

Alice and Bob are playing a game on this graph. First Alice chooses to play as either "increasing" or "decreasing" for herself, and Bob gets the other choice. Then she places a token on any node of the graph. Bob then moves the token along any edge incident to that node. They now take turns playing the following game, with Alice going first.

The current player must move the token from the current vertex to some adjacent unvisited vertex. Let w be the last weight of the last edge that was traversed. The edge that is traversed must be strictly greater than w if the player is playing as "increasing", otherwise, it must be strictly less. The first player unable to make a move loses.

You are given n and the edge weights of the graph. You can choose to play as either Alice or Bob, and you will play against the judge. You must win all the games for your answer to be judged correct.

Interaction

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 50). Description of the test cases follows.

Each test starts with an integer n (1 ≤ n ≤ 50) — the number of nodes on each side of the bipartition.

The next n lines contain n integers a_{ij} (1 ≤ a_{ij} ≤ n^2). a_{ij} denotes the weight of the edge between node i and node j+n. All a_{ij} will be distinct.

You first print a string "A" or "B", denoting which player you want to play ("A" for Alice and "B" for Bob).

If playing as Alice, first print either "I" or "D" (denoting whether you choose "increasing" or "decreasing"). Then, print the node that you wish to start at.

If playing as Bob, read in a character "I" or "D" (denoting whether the judge chose "increasing" or "decreasing"), then the node that the judge chooses to start at.

To make a move, print the index of the node that you wish to go to. To read what move the judge made, read an integer from standard in.

If the judge responds with -1, then that means the judge has determined it has no legal moves (or it may have just given up) and that you won the case. Stop processing this case immediately and start processing the next case.

If the judge responds with -2, that means that the judge has determined that you made an invalid move, so you should exit immediately to avoid getting other verdicts.

If you are unable to make a move or give up, print -1 and then exit immediately. This will give you a Wrong answer verdict.

After printing a move do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer t (t=1).

The second line should contain an integer n (1 ≤ n ≤ 50).

The next n lines should contain n integers each, the a_{ij} (1 ≤ a_{ij} ≤ n^2). a_{ij} denotes the weight of the edge between node i and node j+n. All a_{ij} must be distinct.

The judge will play a uniformly random legal move with this case versus the hacked program. If it has no legal moves left, it will give up and declare the player as the winner.

Example

Input


2
3
3 1 9
2 5 7
6 4 8
6
-1
1
1
I 1
-1

Output


A
D 3
2
B
2

Note

The first example has two test cases. In the first test case, the graph looks like the following.

<image>

In the sample output, the player decides to play as Alice and chooses "decreasing" and starting at node 3. The judge responds by moving to node 6. After, the player moves to node 2. At this point, the judge has no more moves (since the weight must "increase"), so it gives up and prints -1.

In the next case, we have two nodes connected by an edge of weight 1. The player decides to play as Bob. No matter what the judge chooses, the player can move the token to the other node and the judge has no moves so will lose.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;
 
import static java.lang.Math.*;
 
public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
        
        public int read() {
            if (numChars==-1) 
                throw new InputMismatchException();
            
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
                
                if(numChars <= 0)               
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
            
            while(isSpaceChar(c)) 
                c = read();
            
            int sgn = 1;
            
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            
            int res = 0;
            do {
                if(c<'0'||c>'9') 
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c)); 
            
            return res * sgn;
        }
        
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
        
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } 
            while (!isSpaceChar(c));
            
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
        
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    public static void main(String args[]) throws Exception {
        new Thread(null, new Main(),"Main",1<<27).start();
    } 
    public void run() {
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);

        int t = sc.nextInt();

        for(int x = 0; x < t; ++x) {
            int n = sc.nextInt();

            int weight[][] = new int[n][n];
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j)
                    weight[i][j] = sc.nextInt();
            }

            w.println("B");
            w.flush();

            char type = sc.next().charAt(0);
            int node = sc.nextInt() - 1;

            int situation = 0;
            if(node >= n)
                situation ^= 1;

            if(type == 'D') {
                situation ^= 1;
            }

            int preferences[][] = new int[2 * n][n];

            if(situation == 0) {
                for(int i = 0; i < n; ++i) {
                    Pair p[] = new Pair[n];
                    for(int j = 0; j < n; ++j) {
                        p[j] = new Pair(n + j, weight[i][j]);
                    }
                    Arrays.sort(p, new Comparator<Pair>() {
                        public int compare(Pair p1, Pair p2) {
                            return p1.val - p2.val;
                        }
                    });
                    for(int j = 0; j < n; ++j)
                        preferences[i][j] = p[j].ind;
                }

                for(int i = 0; i < n; ++i) {
                    Pair p[] = new Pair[n];
                    for(int j = 0; j < n; ++j) {
                        p[j] = new Pair(j, weight[j][i]);
                    }
                    Arrays.sort(p, new Comparator<Pair>() {
                        public int compare(Pair p1, Pair p2) {
                            return p2.val - p1.val;
                        }
                    });

                    for(int j = 0; j < n; ++j)
                        preferences[n + i][j] = p[j].ind;
                }
            }
            else {
                for(int i = 0; i < n; ++i) {
                    Pair p[] = new Pair[n];
                    for(int j = 0; j < n; ++j) {
                        p[j] = new Pair(n + j, weight[i][j]);
                    }
                    Arrays.sort(p, new Comparator<Pair>() {
                        public int compare(Pair p1, Pair p2) {
                            return p2.val - p1.val;
                        }
                    });
                    for(int j = 0; j < n; ++j)
                        preferences[i][j] = p[j].ind;
                }

                for(int i = 0; i < n; ++i) {
                    Pair p[] = new Pair[n];
                    for(int j = 0; j < n; ++j) {
                        p[j] = new Pair(j, weight[j][i]);
                    }
                    Arrays.sort(p, new Comparator<Pair>() {
                        public int compare(Pair p1, Pair p2) {
                            return p1.val - p2.val;
                        }
                    });

                    for(int j = 0; j < n; ++j)
                        preferences[n + i][j] = p[j].ind;
                }
            }

            int match[] = StableMarriage.findStableMarriage(preferences);
            while(node != -2) {
                w.println((match[node] + 1));
                w.flush();
                node = sc.nextInt() - 1; 
            }
        }

        w.close();
    }
}
class Pair {
    int ind, val;
    Pair(int a, int b) {
        ind = a;
        val = b;
    }
}
class StableMarriage {
    static int[] findStableMarriage(int[][] preferences) {
        // Also known as Gale-Shapley algorithm

        // 0 - (n - 1) ids are man, rest are woman
        // preferences is a 2n (first n man and last n woman) x n matrix which gives person id's sorted rank wise
        // match is an array of size 2*n - matched person for each id

        int n = preferences.length / 2;

        int[] match = new int[2 * n];
        Arrays.fill(match, -1);

        // A rank matrix of n x n, determines rank of each man for each woman
        int rank[][] = new int[n][n];
        for(int j = n; j < 2 * n; ++j) {
            for(int i = 0; i < n; ++i) {
                rank[j - n][preferences[j][i]] = i;
            }
        }

        Queue<Integer> notMatched = new LinkedList<>();
        for(int i = 0; i < n; ++i)
            notMatched.add(i);

        int nextRankToBeProposed[] = new int[n];

        while(!notMatched.isEmpty()) {
            int ind = notMatched.poll(); // current man who will propose

            while(true) {
                int j = preferences[ind][nextRankToBeProposed[ind]++]; // woman to be proposed

                if(match[j] == -1) { // if woman not matched yet
                    match[ind] = j;
                    match[j] = ind;
                    break;
                }
                else if(rank[j - n][match[j]] > rank[j - n][ind]) { // if this man more preferable
                    match[match[j]] = -1;
                    notMatched.add(match[j]); // previous man needs to propose again
                    match[ind] = j;
                    match[j] = ind;
                    break;
                }
            }
        }

        // if(!stable(preferences, match))
        //     System.out.println("Wrong code");

        return match;
    }
    static boolean stable(int[][] preferences, int[] match) {
        int n = match.length / 2;

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(match[i] == j + n)
                    continue;

                int flag = 0;
                for(int k = 0; k < n; ++k) {
                    if(preferences[i][k] == match[i])
                        break;

                    if(preferences[i][k] == j + n) {
                        flag++;
                        break;
                    }
                }
                for(int k = 0; k < n; ++k) {
                    if(preferences[j + n][k] == match[j + n])
                        break;

                    if(preferences[j + n][k] == i) {
                        flag++;
                        break;
                    }
                }
                if(flag == 2)
                    return false;
            }
        }

        return true;
    }
}