B. Deadly Laser

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);
#define Bye return 0
#define CodeTyper main
using ll = long long;

using namespace std;

const int SZ = 2e5+1, mod = 1e9 + 7;

int distance(int x1, int y1, int x2, int y2){
    return abs(x1-x2) + abs(y1-y2);
}

bool isValid(int i, int j, int n, int m){
    return i>=1 && i<=n && j>=1 && j<=m;
}

int dp[3001][3001];
bool vis[3001][3001];
int dy[] = {0, -1, 0};
int dx[] = {-1, 0, 1};

void run_case() {
    int n, m, sx, sy, d; cin>>n>>m>>sx>>sy>>d;
    for (int i = 1; i<=n; i++){
        for (int j = 1; j<=m; j++){
            dp[i][j] = 0;
            vis[i][j] = false;
        }
    }

    queue<pair<int, int>> q;
    q.push({n, m});

    while(!q.empty()){
        pair<int, int> p = q.front();
        int i = p.first, j = p.second;
        q.pop();

        vis[i][j] = true;

        if(distance(sx, sy, i, j)<=d)
            continue;

        for (int x = 0; x<3; x++){
            int ii = i + dy[x];
            int jj = j + dx[x];

            if(isValid(ii, jj, n, m) && distance(sx, sy, ii, jj)>d && vis[ii][jj] == false){
                dp[ii][jj] = dp[i][j] + 1;
                q.push({ii, jj});
            }
        }
    }
/*
    for (int i = 1; i<=n; i++){
        for (int j = 1; j<=m; j++){
            cout<<dp[i][j]<<" ";
        } cout<<endl;
    } cout<<endl;*/

    cout<<(dp[1][1] == 0 ? -1 : dp[1][1])<<endl;
}

int CodeTyper()
{
    IOS;
    int t; cin>>t;
    while(t--) run_case();
    Bye;
}

/*
    * Think first, then code. - CodeTyper
    ** Think twice, code once. - CodeTyper
*/