Given a chess board of order N x M and source points (s1, s2) and destination points (d1, d2). The task to find minimum number of moves required by the Knight to go to the destination cell.

The task to find a minimum number of moves required by the Knight to go to the destination cell.

Given a chessboard of order N x M and source points (s1, s2) and destination points (d1, d2). The task to find the minimum number of moves required by the Knight to go to the destination cell.

For each test case in a new line print the minimum number of moves required by the knight to go to the destination from the source. If no such move is possible print -1.

Example:
Input:
2
4 7
2 6 2 4
7 13
2 8 3 4

Output:
2
3

#include <bits/stdc++.h>

#include<tuple>

using namespace std;

int main() {

    int t;

    cin >> t;

    while (t--) {

        int n, m, x, y, l, p = -1, k = 0, h;

        cin >> n >> h;

        cin >> x >> y;

        cin >> l >> m;

        queue < tuple < int, int, int > > q;

        q.push(make_tuple(l, m, 0));

        int a[n + 1][h + 1];

        a[l][m] = 1;

        memset(a, 0, sizeof(a));

        while (!q.empty()) {

            l = get < 0 > (q.front());

            m = get < 1 > (q.front());

            k = get < 2 > (q.front());

            q.pop();

            if (l == x && m == y) {

                p = k;

                break;

            }

            ++k;

            if (l - 1 > 0 && m + 2 <= h && a[l - 1][m + 2] == 0) {

                q.push(make_tuple(l - 1, m + 2, k));

                a[l - 1][m + 2] = 1;

            }

            if (l + 1 <= n && m + 2 <= h && a[l + 1][m + 2] == 0) {

                q.push(make_tuple(l + 1, m + 2, k));

                a[l + 1][m + 2] = 1;

            }

            if (l - 1 > 0 && m - 2 > 0 && a[l - 1][m - 2] == 0) {

                q.push(make_tuple(l - 1, m - 2, k));

                a[l - 1][m - 2] = 1;

            }

            if (l + 1 <= n && m - 2 > 0 && a[l + 1][m - 2] == 0) {

                q.push(make_tuple(l + 1, m - 2, k));

                a[l + 1][m - 2] = 1;

            }

            if (l - 2 > 0 && m + 1 <= h && a[l - 2][m + 1] == 0) {

                q.push(make_tuple(l - 2, m + 1, k));

                a[l - 2][m + 1] = 0;

            }

            if (l - 2 > 0 && m - 1 > 0 && a[l - 2][m - 1] == 0) {

                q.push(make_tuple(l - 2, m - 1, k));

                a[l - 2][m - 1] = 1;

            }

            if (l + 2 <= n && m + 1 <= h && a[l + 2][m + 1] == 0) {

                q.push(make_tuple(l + 2, m + 1, k));

                a[l + 2][m + 1] = 1;

            }

            if (l + 2 <= n && m - 1 > 0 && a[l + 2][m - 1] == 0) {

                q.push(make_tuple(l + 2, m - 1, k));

                a[l + 2][m - 1] = 1;

            }

        }

        cout << p << endl;

    }

    return 0;

}