By applying appropriate rotation, translation, and flip, it can be boiled down to the case where \(0 \leq S_x < K, 0 \leq S_y < K, 0 \leq T_x\), and \(0 \leq T_y\). Hereinafter we assume them.

Let \(i,j\), and \(k\) be the integers such that \((T_x + 0.5, T_y + 0.5)\) is contained in tile \((i, j, k)\).

The essential part of this problem is casework. For example, the answer can be always found using a simple algorithm with a constant number of parameters: whether \(i = j = 0\), the value \(\max(S_y, K - 3)\), the value \(\min(k, 2)\), whether \(K = 2\), and the parities and ordering of \(i\) and \(j\).

First, we consider the case where \(i = j = 0\). It is easy to check whether the answer is \(0\) or \(1\). Other destinations \((i, j, k)\) can be reached with two moves via tile \((1, 0, 0)\).

From now on, we assume that \(i \neq 0\) or \(j \neq 0\).

By induction, it turns out that the answer is independent of \(S_y\) if \(S_y \leq K - 3\) (which allows us to assume that \(S_y = K - 3\)). Similarly, the answer is independent of \(k\) if \(k \geq 2\).

Moreover, let \(f_0\) be the number of moves required to reach tile \((i, j, k)\), and \(f_0\) that for tile \((i - 1, j - 1, k)\); then it can be proved that \(f_0 = f_1 + 2\) if \(i > 0, j > 0\), and \((i, j) \neq (1,1)\).

Therefore, it is sufficient to resolve the case where \(i = 0, j = 0, (i, j) = (1, 1)\).

The answer to these individual cases can be represented by a very simple expression. Exceptionally, if \(K = 2\), some approaches may require additional casework.

One possible approach is as follows: let \(g_0\) be the number of moves required to reach \((0, j, k)\), and \(g_1\) for \((0, j - 2, k)\); then for \(j \leq 3\), we can use the relation \(g_0 = g_1 + 3\) if \(K = 2\) and \(K \neq 2\) if \(g_0 = g_1 + 4\). The same kind of relations also hold for \(j = 0\) case.

Hence, each test case can be answered with a constant number of computation.

The proof may be simplified by using the fact that either \(x \geq 0\) or \(y \geq 0\) always holds, or considering the set of tiles reachable in \(n\) or less moves recursively.

If you are not sure about the casework, we recommend you to write a naive solution using 01-BFS (Breadth-First Search) for example, and check if your solution always prints the correct answer for various cases.