Superpiece

You are given an infinite chessboard. In this task, a chessboard is an infinite two-dimensional grid of squares, where each square is indexed by a pair of integers (r, c), denoting the row and the column respectively. The only piece currently present on the chessboard is the superpiece. You are given a list of valid moves of your superpiece, which will be specified as a non-empty string containing a subset of the characters in "QRBNKP". In each turn, the superpiece can move as one of the given chess pieces. The superpiece is initially positioned at square (a, b). Calculate the minimum number of moves needed to reach the square (c, d).

The subset of the chess rules applicable for this problem are given below.

There are six types of pieces: queen, rook, bishop, knight, king and pawn. They move the following way:

• The Queen (denoted by 'Q') can move to any square in the same row, column or diagonal as the square it is currently in. Formally, for any integer k ≠ 0, a queen can move from (a, b) to (a, b + k), (a + k, b), (a + k, b + k) and (a + k, b − k).

• The Rook (denoted by 'R') can move to any square in the same row or in the same column as the square it is currently in. Formally, for any integer k ≠ 0, a rook can move from (a, b) to (a + k, b) and (a, b + k).

• The Bishop (denoted by 'B') can move to any square in the same diagonal as the square it is currently in. Formally, for any integer k ≠ 0, a bishop can move from (a, b) to (a + k, b + k), and (a + k, b − k).

• The kNight (denoted by 'N') can move in the shape of an 'L': that is, it first moves two squares in a particular direction followed by a move of one sqaure in an perpendicular direction. Formally, a knight can move from (a, b) to (a + 1, b + 2), (a + 1, b − 2), (a + 2, b + 1), (a + 2, b − 1), (a − 2, b + 1), (a − 2, b − 1) (a − 1, b + 2) and (a − 1, b − 2).

• The King (denoted by 'K') can move to any of the eight squares directly adjacent to the current square. Formally, a king can move from (a, b) to (a, b + 1), (a, b − 1), (a + 1, b), (a − 1, b), (a + 1, b + 1), (a + 1, b − 1), (a − 1, b + 1) and (a − 1, b − 1).

• The Pawn (denoted by 'P') can move exactly one square up. Formally, a pawn can move from (a, b) to (a + 1, b).

Note that the other rules or moves that you might know about chess do not apply in this problem; please only use the ones listed above.

Also, note that while the symbol denoting the chess piece is often the first letter of its name in English, it is the second letter for the "kNight" (to avoid confusion with the "King").

The first line of the input contains an integer q, representing the number of queries your program will be tested on. Each two of the following lines describe a query:

• The first line of a query contains a non-empty string specifying the set of chess pieces the superpiece can move as. This string contains a subset of the characters in the uppercase string "QRBNKP", with the contained characters appearing in the same order. In other words, it is in the form of a sub-sequence of "QRBNKP".
• The second line of a query contains four space-separated integers a, b, c, d - the original and the target position of the superpiece. It is guaranteed that (a, b) ≠ (c, d), that is, the original position is different from the target.

For each of the q queries, output a single line containing an integer m representing the minimum number of moves the superpiece needs to reach the target from its original position for that query. If it is not possible to reach the target from the original position for a query, output −1 instead.

• 1 ≤ q ≤ 1000
• -108 ≤ a, b, c, d ≤ 108 for each query.
• The chess board is infinite in all directions.