C. Knight
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As Colette learns the rules of chess, she becomes intrigued by a particular piece: the knight. Its movement is notably distinct from that of other pieces. As a reminder, a knight can perform one of the following moves, with the crucial condition that the destination square must lie within the boundaries of the chessboard:

  • Move $$$k$$$ squares horizontally, and then $$$1$$$ square vertically.
  • Move $$$1$$$ square horizontally, and then $$$k$$$ squares vertically.

For a standard knight, $$$k=2$$$.

Colette wants to solve the knight traversal problem for an arbitrary integer $$$k$$$. She considers a chessboard with $$$n$$$ rows (numbered $$$1$$$ to $$$n$$$) and $$$m$$$ columns (numbered $$$1$$$ to $$$m$$$). She places a knight, which uses this specific move parameter $$$k$$$, initially at the $$$i$$$-th row and $$$j$$$-th column of this chessboard. Colette's goal is to determine how many distinct squares on this $$$n \times m$$$ chessboard the knight can visit by moving any number of times (possibly zero). Can you help her?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The single line of each test case contains five integers $$$k,n,m,i,j$$$ ($$$1 \le k \le 10^9$$$, $$$1 \le i \le n \le 10^9$$$, $$$1 \le j \le m \le 10^9$$$).

Output

For each test case, output one integer — the number of squares that the knight can visit.

Example
Input
4
1 3 2 2 1
2 3 3 2 2
2 3 3 1 1
3 4 5 1 2
Output
3
1
8
9
Note

The first three example cases are illustrated in the figures below. Note that in the third figure, the variation in color is used in this instance primarily for visual clarity to help distinguish individual arrows.