Knight Probability in Chessboard

Calculate the probability that a knight remains on an N x N chessboard after making K moves. Initially, the knight is placed at a given position on the board. It can move in any of the 8 directions it is allowed to on a chessboard.

The knight's potential moves from any position (i, j) are: (i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1), (i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), and (i - 1, j - 2).

Input:

The first line contains an integer, 'T', denoting the number of test cases. Each test case starts with two integers, 'N' and 'K', which denote the chessboard's dimension and the number of moves the knight must make. The next line of each test case contains two integers, 'Sx' and 'Sy', representing the knight's initial position.

Output:

For each test case, print the probability that the knight remains on the chessboard after all moves. Ensure the output is accurate to six decimal places.

Example:

Input:

2
8 3
0 0
10 7
5 5

Output:

0.125000
0.981250

Constraints:

• 1 <= T <= 5
• 0 <= N <= 30
• 0 <= K <= 500
• 0 <= Sx, Sy <= N - 1

Time Limit: 1 sec.

Note:

Consider all possible sequences of the knight's moves to determine its likelihood of staying on the board.