In this problem Benny is looking for your help as usual.

There are N baskets, which are numbered from 0 to N - 1.

In each moment of time exactly, starting with t = 1, one ball appears in x_i-th basket, where x_i = (a * x_(i-1) + b) % N.

The bottom of the i-th basket opens when there is not less than the p[i] balls in it, all the balls fall out of the basket, and then the bottom of the basket is closed again.

How many times baskets' bottoms will open to the T-th moment of time?

Input

The first line containts Q - the amount of test cases.

Each test case consist of three lines:

First line contains N

Second line contains N numbers p[i]

Third line contains x₁ , a, b, t

x_i = (a * x_i-1 + b) % N;

Output

Q lines - answers for each case

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10
• 1 ≤ p[i] ≤ 10⁵
• 1 ≤ A, B ≤ 10⁹
• 0 ≤ X < N
• 0 ≤ t < 10⁶