M. Modular Universe
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the modular universe, everything is modular, even coordinates!

For example, if someone has coordinates $$$(x,y)$$$ in the normal universe, they will have coordinates $$$(x \bmod n,y\bmod m)$$$ in some modular universe, where $$$(n,m)$$$ is the modularity of that universe.

Now, $$$n\times m$$$ people live in the $$$(n,m)$$$-modular universe. They are usually found at different positions in the universe, but there is always a day called the singularity day, where all the population will gather at the same coordinate $$$(0,0).$$$ This is a very special holiday as only singularity days have this property.

Once the singularity day finishes, for each $$$k\in\{0,\dots,nm-1\},$$$ the $$$k^\text{th}$$$ person will go to the point $$$\left((k \ \text{div} \ m ) \bmod n, k\bmod m\right)$$$ on the next day, and from there on, that person will continue their journey to $$$((2k \ \text{div} \ m) \bmod n, 2k\bmod m),((3k \ \text{div} \ m) \bmod n, 3k\bmod m),\text{etc}\dots$$$ in the subsequent days.

Now, the most important phenomenon in history is the modular big bang, which is the only day in history on which all modular universes have a singularity day at the same moment.

You are from universe $$$(0,0),$$$ where you don't have modular coordinates, and you are asked to inquire more intel about the patterns of universe $$$(n,m).$$$ You will do that by inspecting the number of people residing in the same point $$$(x,y)$$$ during some day $$$d.$$$

Your supervisors shared with you some important intel, which is the day on which the modular big bang occurred.In fact, it is denoted as day $$$0$$$ by your agency's convention. They sent you also $$$Q$$$ queries, where each one is of the form '$$$\mathtt{n\ m\ x\ y\ d}$$$'. For each one of these queries, you have to find the number of people residing in point $$$(x,y)$$$ on day $$$d$$$ in the $$$(n,m)$$$-modular universe. Good luck with that!

Input
  • The first line contains an integer $$$1\le Q \le 10^5$$$ denoting the number of queries.
  • Each of the following $$$Q$$$ lines contains $$$5$$$ integers $$$n,m,x,y,d$$$ where:
    • $$$1\le n,m \le 10^9:$$$ The modularity of the universe.
    • $$$0 \le x < n$$$ and $$$0\le y < m:$$$ The coordinates of the inspected position.
    • $$$0\le d\le 10^9:$$$ The day of inspection, with respect to the modular Big Bang.
Output

For each query, output one integer $$$r$$$ denoting the number of persons residing at position $$$(x,y)$$$ during day $$$d$$$ in the universe $$$(n,m).$$$

Example
Input
5
1 1 0 0 1
2 2 0 0 1
10 20 0 0 30
10 20 3 1 16
10 20 0 0 5
Output
1
1
100
0
25
Note

In the queries, the time is represented with respect to the modular Big Bang. In fact, day $$$d$$$ means $$$d$$$ days since the Big Bang. In particular, day $$$0$$$ is the day of the modular Big Bang.