Keshri and his friend Akshay are having a fight about who will eat the last apple. Since they both love to eat, so to arrive at a conclusion, their friend Ankur gives them a question about trees, he calls the tree as - Apple Tree.

He gave them a binary apple tree consisting of 'n' nodes, where the value in each node denotes the number of apples in that node. He tells them to find the number of nodes, such that for each node, the following condition holds true:

'max_i' is a prime number,

where max_i = maximum number of apples which you can get from the sub-tree of the ith node (including the apples of ith node), under the condition that you are allowed to choose only ONE node in that sub-tree to collect apples. where 1 ≤ i ≤ n.

The one who finds the answer correctly can have the last apple. Since, you being a friend of Keshri, he asks you to help him with this problem.

Input:-
First line consists of 't', denoting the number of test cases.
Then each of the 't' lines contains the following:

'n', denoting the number of nodes in the Apple tree, followed by 'n-1' lines in the form of 'u v', denoting 'u' is the parent of 'v' in the tree.
Then in another line, 'n' space-separated integers denoting the number of apples in each node of the tree. In the last line, 's', denoting the root node of the tree.

Output:-
Print 't' lines (for all the test cases), the answer to the above question.

Constraints:-
1 <= t <= 20
1 <= (number of apples in each node) <= 10^7
1 <= s <= n
1 <= u,v <= n (where u and v are different, also no edge is repeated in the input provided)
1 <= n <= 10^6

Problem Setter:-
Devesh Jagwani