int travel (int n, int a, int b) {
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    queue<vector<pair<int, int>>> Q;
    Q.push({{0, 0}});
    while (!Q.empty()) {
        vector<pair<int, int>> T = Q.front();
        Q.pop();
        int x = T.back().first;
        int y = T.back().second;
        vector<int> one = {-1, 1};
        set<pair<int, int>> neighbours;;
        for (int i : one) {
            for (int j : one) {
                neighbours.insert({x+i*a, y+j*b});
                neighbours.insert({x+i*b, y+j*a});
            }
        }
        for (auto p : neighbours){
            int x2 = p.first, y2 = p.second;
            if (x2 == n-1 and y2 == n-1) return T.size();
            if (0 <= x2 and x2 < n and 0 <= y2 and y2 < n and !visited[x2][y2]) {
                vector<pair<int, int>> history = T;
                history.push_back({x2, y2});
                Q.push(history);
                visited[x2][y2] = true;
            }
        }
    }
    return -1;
}

vector<vector<int>> knightlOnAChessboard(int n) {
    vector<vector<int>> answer(n-1, vector<int>(n-1));
    for (int i=1; i < n; i++) {
        for (int j=1; j < n; j++) {
            answer[i-1][j-1] = travel(n, i, j);
        }
    }
    return answer;
}

int BFS(int i,int j,int n){
    queue<pair<pair<int,int>,int>> q;
    int id[n][n];
    memset(id,0,sizeof(id));
    id[0][0]=1;
    vector<pair<int,int>> move={{i,j},{i,-j},{-i,j},{-i,-j},{j,i},{j,-i},{-j,i},{-j,-i}};
    q.push({{0,0},0});
    
    while(!q.empty()){
        int x=q.front().first.first,y=q.front().first.second,count=q.front().second;
        for(int i=0;i<8;i++){
            int tempx=x+move[i].first,tempy=y+move[i].second;
            if(tempx>=0 && tempy>=0 && tempx<n && tempy<n && id[tempx][tempy]==0){
                q.push({{tempx,tempy},count+1});
                id[tempx][tempy]=1;
            }
        }
        if(x==n-1 && y==n-1)
            return count;
        q.pop();
    }
    return -1;
}

vector<vector<int>> knightlOnAChessboard(int n) {
    int d=n-1;
    vector<vector<int>> ans(d,vector<int>(d,0));
    for(int i=0;i<d;i++){
        for(int j=0;j<d;j++){
            if(i==j){
                if(d%(i+1)==0) ans[i][j]=d/(i+1);
                else ans[i][j]=-1;
            }
            else{
                if(ans[i][j]==0){
                    ans[i][j]=BFS(i+1,j+1,n);
                }
                ans[j][i]=ans[i][j];
            }
        }
    }
    return ans;
}

class Result {

/*
 * Compute minimal distance for a knight making L-shaped moves.
 *
 * Notes: Essentially a mere implementation problem, but we can
 * parallelize the search, and store identical states (homologs).
 *
 * Uses a reductive design for potential concurrency gains,
 * backed by a Red-Black Tree of dependencies (ConcurrentHashMap).
 * (remove .parallel for sequential hardware)
 *
 * 𝚯(N) runtime for each Knight, given N = board size (n * n).
 *
 * Total runtime 𝚯(N log N) with unlimited processors and neighbor
 * reducing on, otherwise 𝚯(knights * searches) = 𝚯(n * N) = 𝚯(n³).
 *
 * 𝚯(N) space complexity for each search
 */
static Map<Set<Integer>, Integer> memo = new ConcurrentHashMap<>();
public static List<List<Integer>> knightOnAChessboard(int n) {
    return IntStream.range(1, n)
            .parallel()
            .mapToObj(x -> IntStream.range(1, n)
               .parallel()
               .map(y -> memoize(new Knight(x, y, n)))
        .boxed().toList()).toList();
}

/* Store mirrors of this Knight for simple dynamic programming. */
private static Integer memoize(Knight k) {
    return memo.merge(k.homolog(), distanceOf(k), (a, b) -> a);
}

/* Compute the board distance for this Knight, via BFS */
private static Integer distanceOf(Knight k) {
    final Point destination = new Point(k.n - 1, k.n - 1);
    final Point origin  = new Point(new Point(0, 0));
    Deque<Point> queue = new ArrayDeque<>(List.of(origin));
    Set<Point> alreadyVisited = new HashSet<>(List.of(origin));
    k.atlas.put(origin, 0);

    do {
        Point current = queue.remove();
        if (current.equals(destination)) {
            return k.atlas.get(current);
        } else {
            alreadyVisited.add(current);
            queue.addAll(k.neighborsOf(current));
            queue.removeAll(alreadyVisited);
        }
    } while (!queue.isEmpty());
    return -1;
 }
}

/*
 * Knight moving in (dx, dy) fashion on chessboard.
 * The knight keeps an 'odometer' of the minimum moves
 * to reach a given square.
 */
class Knight {

Map<Point, Integer> atlas = new ConcurrentHashMap<>();
final int x; final int y; final int n;
Knight(int x, int y, int n) {
    this.x = x;
    this.y = y;
    this.n = n;
}
/* Enumerate all positions reachable by this Knight */
public List<Point> neighborsOf(Point p) {
    return Direction.all()
            .flatMap(d -> travel(p, d))
            .filter(this::isValid)
            .toList();
}
private Stream<Point> travel(Point p, Direction d) {
    return Stream.of(pointOf(p, d, x, y), pointOf(p, d, y, x));
}
private Point pointOf(Point p, Direction sign, int dx, int dy) {
    Point q = p.getLocation();
    q.translate(dx * sign.dx, dy * sign.dy);
    atlas.merge(q, atlas.get(p) + 1, Math::min);
    return q;
}
/* Represent the cardinal directions */
private enum Direction {
    U(1,1),
    D(-1,-1),
    L(-1, 1),
    R(1, -1);
    final int dx; final int dy;
    private Direction(int dx, int dy) {
        this.dx = dx;
        this.dy = dy;
    }
    static Stream<Direction> all() {
        return Arrays.stream(Direction.values());
    }
}
private boolean isValid(Point p) {
    return p.y < n && p.x < n && p.y >= 0 && p.x >= 0;
}
Set<Integer> homolog() {
    if(x == y)
        return Set.of(x);
    return Set.of(x, y);
  }
}