for integers a_1,a_2,...a_n and b.

Constraints

0 < n < 10^3
0 < a_1,a_2,...a_n,b < 10^6

Input

The first line is the number of test cases to follow (less than 100), which are separated by blank lines, and each of which has the form:

n
a_1 a_2 ...a_n
b

Output

Output the answers, in order, on separate lines.

Example

Input:
5

2
2 3
3

3
1 1000 3142
2

1
8
1

3
12 15 2
18

4
10 10 10 34
42

Output:
2
1
0
0
4