#include #define pb push_back #define ff first #define ss second #define mpa make_pair using namespace std; typedef long long LL; bool valid(int x, int y, int N, int M) { if(x <= 0 || y <= 0 || x > N || y > M) return false; return true; } int bfs(pair p1, pair p2, pair p3, int dx[], int dy[]) { int N = p3.ff; int M = p3.ss; queue, int> > Que; map, bool> Vis; Que.push(mpa(p1, 0)); while(!Que.empty()) { pair, int> temp = Que.front(); Que.pop(); if(temp.ff.ff == p2.ff && temp.ff.ss == p2.ss) return temp.ss; int x = temp.ff.ff; int y = temp.ff.ss; int dis = temp.ss + 1; if(Vis.count(mpa(x, y))) continue; Vis[mpa(x, y)] = true; for(int i = 0; i < 8; ++i) { int x1 = x + dx[i]; int y1 = y + dy[i]; if(valid(x1, y1, N, M)) Que.push(mpa(mpa(x1, y1), dis)); } } return -1; } int solve(int N, int M, int x1, int y1, int x2, int y2, int dx[], int dy[]) { pair p1; p1.ff = x1; p1.ss = y1; pair p2; p2.ff = x2; p2.ss = y2; pair p3; p3.ff = N; p3.ss = M; int ans = bfs(p1, p2, p3, dx, dy); return ans; } int main() { int n; cin>>n; for(int i = 1; i #define ll long long #define mod 1000000007 using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i = 1; i