Prime Team

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.

Input

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.

Output

Print an integer k — the maximum number teams that can be formed without violating the rules.

Sample

Input	Output
7 1 9 4 3 8 5 2	3
One possible way to form 3 teams is: Team-1 → 1st and 4th player, jersey number [1, 3] Team-2 → 2nd and 6th player, jersey number [9, 5] Team-3 → 3rd and 7th player, jersey number [4, 2]