Back

Ulam's Spiral

Worth 6 point(s) - Runtime Limit: 1 seconds

Introduction

In 1963, a bored Stanislaw Ulam at a science meeting began to doodle on some paper he had at hand. One of his doodles included listing the natural numbers in a spiral, as follows.

Ulam then noticed a pattern regarding his spiral and the prime numbers. Prime numbers tend to be found in diagonal lines across the spiral. This holds true if the starting number in the spiral is a number other than 1. To keep track of the positioning of these numbers, we will use Cartesian coordinates with the starting number at (0, 0), the second at (1, 0), and the third at (1,1). For example, in the spiral shown above, (1, 3) maps to 33 and (-2, 2) maps to 17. Given the value at (x1, y1), find the value at (x2, y2). Keep in mind that the spiral can start at any integer value but always increments by 1.

Input:
The first line of input contains an integer D, denoting the number of test cases. The following D lines contain 5 integers, x1, y1, x2, y2, and k, respectively, denoting the value at (x1, y1) as k and prompting the value at (x2, y2). Assume that -500 ≤ x1, y1, x2, y2 ≤ 500.

Output:
For each test case, print a line containing the value at (x2, y2).

Sample Input

3
1 2 -3 2 20
-1 -1 1 1 2
3 3 0 0 40

Sample Output

44
-2
10