There are n players standing in a line. Each of the players is assigned a unique jersey number.
You have to form as many team as possible satisfying the following rules.
1. Each team will contain two players. One of them will lead the team.
2. The jersey number of the leader must be a prime number.
You are given the jersey number of each player. Find the maximum number teams can be formed without violating the rules.
First line of the input contains an integer n(1 ≤ n ≤ 100) — The number of players.
Second line contains n space-separated integers a1, a2,…, an (1 ≤ ai ≤ 1000), where ai denotes the jersey number of the ith player.
Print an integer k — the maximum number teams that can be formed without violating the rules.
7 1 9 4 3 8 5 2
One possible way to form 3 teams is: