There is a game where you need to move through a labyrinth. The labyrinth consists of $$$n$$$ platforms, connected by $$$m$$$ passages.

Each platform is at some level $$$l_i$$$, an integer number from $$$0$$$ to $$$H - 1$$$. In a single step, if you are currently on platform $$$i$$$, you can stay on it, or move to another platform $$$j$$$. To move to platform $$$j$$$ they have to be connected by the passage, and their levels have to be the same, namely $$$l_i = l_j$$$.

After each step, the levels of all platforms change. The new level of platform $$$i$$$ is calculated as $$$l'_i = (l_i + s_i) \bmod H$$$, for all $$$i$$$.

You start on platform $$$1$$$. Find the minimum number of steps you need to get to platform $$$n$$$.

Input

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$H$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m \le 10^5$$$, $$$1 \le H \le 10^9$$$).

The second line contains $$$n$$$ integers $$$l_i$$$, the initial level of each platform ($$$0 \le l_i \le H-1$$$).

The third line contains $$$n$$$ integers $$$s_i$$$, the change of level for each platform ($$$0 \le s_i \le H-1$$$).

Next $$$m$$$ lines contain a description of the passages. Each passage is described as a pair of integers — the platforms, connected by the passage. There is at most one passage connecting each pair of platforms, and there is no passage connecting a platform to itself.

The sum of $$$n$$$ for all tests does not exceed $$$10^5$$$, the sum of $$$m$$$ for all tests does not exceed $$$10^5$$$.

Output

For each test case, print a single integer, the minimum number of steps needed to get from platform $$$1$$$ to platform $$$n$$$.

If it is impossible to get to platform $$$n$$$, print $$$-1$$$.

Note

This is how levels of the platforms change, and what actions we need to perform in the first example.

	Platform 1	Platform 2	Platform 3	Action
Step 1	1	9	4	Stay on the platform 1
Step 2	3	2	4	Stay on the platform 1
Step 3	5	5	4	Move to the platform 2
Step 4	7	8	4	Stay on the platform 2
Step 5	9	1	4	Stay on the platform 2
Step 6	1	4	4	Move to the platform 3

Idx	Name	Rating
A	Thorns and Coins	800
B	Chaya Calendar	1100
C	LR-remainders	1400
D	Card Game	1400
E	Final Countdown	1600
F	Feed Cats	1900
G	Moving Platforms	2300

Codeforces Round 927 (Div. 3)