// Arup Guha
// 5/10/2019
// Solution to 2019 FHSPS Playoff Problem: Energizer Knight

import java.util.*;

public class energizer {
	
	// Knight movement.
	final public static int[] DX = {-2,-2,-1,-1,1,1,2,2};
	final public static int[] DY = {-1,1,-2,2,-2,2,-1,1};	
	final public static int MOD = 10007;
	
	final public static int N = 8;
	public static int[][] kMat;
	
	public static void main(String[] args) {
		
		// Pre-comp this, it's always the same.
		formKMat();
		
		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();
		
		// Process each case.
		for (int loop=0; loop<numCases; loop++) {
			
			// Get input.
			int x1 = stdin.nextInt()-1;
			int y1 = stdin.nextInt()-1;
			int x2 = stdin.nextInt()-1;
			int y2 = stdin.nextInt()-1;
			long dist = stdin.nextLong();
			
			// Ta da!
			int[][] res = fastMatExpo(kMat, dist);
			System.out.println(res[N*x1+y1][N*x2+y2]);
		}
	}
	
	public static int[][] fastMatExpo(int[][] mat, long exp) {
		
		// No work to be done.
		if (exp == 1) return mat;
		
		// This is where we get our speed up!
		if (exp%2 == 0) {
			int[][] sqrt = fastMatExpo(mat, exp/2);
			return multiply(sqrt, sqrt);
		}
		
		// Usual recursion.
		int[][] tmp = fastMatExpo(mat, exp-1);
		return multiply(tmp, mat);
	}
	
	// Standard Matrix Multiply under mod.
	public static int[][] multiply(int[][] a, int[][] b) {
		int[][] res = new int[a.length][b[0].length];
		for (int i=0; i<a.length; i++) 
			for (int j=0; j<b[0].length; j++) 
				for (int k=0; k<b.length; k++)
					res[i][j] = (res[i][j] + a[i][k]*b[k][j])%MOD;
		return res;
	}
	
	// Returns the knight jump matrix. mat[i][j] == 1 iff a knight on square i can
	// jump to square j in one move. Square i is (i/N, i%N).
	public static void formKMat() {
		
		kMat = new int[N*N][N*N];
		
		// i is the starting square (i/N, i%N).
		for (int i=0; i<N*N; i++) {
			
			// Try each place we can go.
			for (int j=0; j<DX.length; j++) {
				int x = i/N + DX[j];
				int y = i%N + DY[j];
				if (!inbounds(x, y)) continue;
				kMat[i][x*N+y] = 1;
			}
		}
	}

	public static boolean inbounds(int r, int c) {
		return r >= 0 && r < N && c >= 0 && c < N;
	}
}