Daenerys now has to conquer the Kingdom of the Mountain and the Vale, ruled by Robin of House Arryn, under the guidance of his mother Lysa. Robin is very afraid of prime numbers. So Daenerys just needs a good formation of the army in order to scare Robin and win the kindgom.

Daenerys has The Unsullied Army at her service. Each soldier has a skill level. Some of these soldiers are friends and hence will form a group. If soldier A & B are friends and soldiers B & C are friends, then A-B-C are part of a single platoon. A prime platoon is one in which the sum of skill levels of the soldiers is a prime number.

Daenerys asks you to calculate the total number of Unsullied Soldiers belonging to such prime platoons so that she can plan her invasion accordingly.

Input

The first line contains T, the number of test cases.

The first line of each test case contains two integers N and M denoting the number of Unsullied and the number of friendships.

The next line contains N space separated integers indicating the skill levels of the unsullied (A_i).

The next M lines contain two integers u and v each indicating that soldiers u & v are friends.

It is guaranteed that the number of prime checks throughout a single test file does not exceed 1,20,000.

Output

The only line of output should contain 1 integer denoting the number of students belonging to prime platoons.

Constraints

1 <= T <= 200

1 <= N <= 10^4

1 <= M <= 2*N

0 <= A_i <= 10^5 for i = 1, 2, .., N

Warning

Large I/O files. Use scanf/printf instead of cin/cout or else use ios::sync_with_stdio(false).