Dexter studies in Huber Elementary School, so does his arch rival Mandark. The school planned a fun trip to a carnival for N students. Everyone’s happy. Mandark has devised a plan to ruin the trip. He knows that there exist many groups within the students. Students of one group are friends with each other but not with any student of other groups. His plan is to instigate a fight among them.

At the carnival, all students line up for time on a trampoline. Dexter learns about Mandark’s plan and knows that If two students that are not friends get on the trampoline at the same time, a fight will start. Suddenly his ‘lab alert’ buzzes. Deedee is trying to break into the lab again! Dexter has to get back home to defend his lab as soon as possible, but he can’t let Mandark ruin the trip.

The trampoline can handle a total weight of W kgs. The students are getting impatient to get on the trampoline. To save time and to avoid a fight, Dexter decides that he will select the first batch of students to go on the trampoline in such a way that their total weight exactly equals W and that no two students are not friends. Your job is to tell him the number of ways he can do this. Dexter has the knowledge of only M pairs of friends.

Input

The first line contains T, the number test cases. T test cases follow. The first line of each test case contains three integers N, W and M. The next line contains N integers, The ith integer is the weight of the ith student (1 <= i <= N). The next M lines contain two integers, q and w; this tells that student q and student w are friends.

Output

For each test case, output a line containing a single integer, the number of ways Dexter can choose the first batch of students to get on the trampoline.

Constraints

1 <= T <= 10

1 <= N <= 22

1 <= q, w <= N

0 <= M <= (N*(N+1))/2

1 <= W <= 1500

1 <= Weight of each student <= 60

Assume that the maximum number of students on the trampoline has no limit. Only the maximum weight on the trampoline has the limit W.

Sample

Input:
2
10 90 5
20 30 10 20 30 50 40 20 40 50
1 2
2 3
3 4
4 5
9 10
5 57 3
20 10 96 20 1
1 2
2 3
1 3

Output:
3
0

Explanation

For first test case, the following three ways are possible. Using student number,

• (1, 2, 3, 5)
• (2, 3, 4, 5)
• (9, 10)

For the second test case, there is no way for the total weight of selected students to be exactly W.