Give you a sequence A of length N. There are N multisets initially, the i^th multiset is {A_i}.

And then there are M operations. In each operation, give you j and k. let S be the multiset A_j belongs to, T be the multiset A_k belongs to. You have to answer how many pairs (a, b) satisfying: a ∈ S, b ∈ T and a > b, and then merge S and T.

The first line of the input gives the number of test cases T. T test cases follow.

Each test case starts with a line consist of two integers N and M. The next line consists of N integers A_i indicating the i^th element in the sequence. Then M lines follow. Each line consists of two integers j and k.

1 ≤ N, M ≤ 10⁵_.

A_i is representable by 32-bit signed integer.

1 ≤ j, k ≤ N for every operation.

1 ≤ T × (N + M) ≤ 4×10⁵.

For each test case, first output one line containing “Case x:”, where x is the test case number.

Then for every operation, output one line consists of one integer indicating the number of pairs (a, b) described above or -1 if A_j and A_k belongs to a same multiset.

2
5 3
1 2 3 4 5
1 2
3 2
1 3
4 4
0 0 1 1
1 2
4 3
3 2
1 4

Case #1:
0
2
-1
Case #2:
0
0
4
-1