DHARMONY - Death to harmony

no tags 

You are very angry at Victor because of his problems with weird statements and subtasks with no real links between them, so you have decided to take revenge. That is, you will break into his house and detune his piano.

Victor's piano is very large and has n ≤ 105 strings, which are all originally tuned to a given integer frequency. You know from music theory that the most important interval in music is the octave, that is, two notes such that the frequency of one of them is the double of the frequency of the other. As a consequence, in order to break the harmony of the piano, you wish to alter the frequencies of some strings such that in the end, there is no pair (i,j) of strings such that the frequency of string i is exactly twice that of string j.

In order to change the strings' frequencies, you own two tuning keys. The first one, called Nimbus440, is very handy and allows you to tune a string to any positive integer frequency in one move (the strings are very strong and can be tuned to arbitrary large frequencies). The second one, called XorOne, is much less useful, and only allows you to increase an even frequency by one, or decrees an odd frequency by one (for example, it can change 4 into 5, or 5 into 4, but not 4 into 3 or 3 into 4). Why do you even have it?

When leaving home to go commit the crime, you were distracted and took one of the two keys at random. Thus you cannot choose which key you'll use. Furthermore, you would like to finish quickly in order not to get caught, so you would like to detune the piano in a minimum number of key uses. Your task is to find this minimum.

Input

The first line of the input contains integer n. The next line contains n space-separated integers, the frequencies fi of the piano strings. The frequencies are not necessarily distinct. The third line contains a word, either "Nimbus440" or "XorOne" (without quotes), which tells you which key you have at your disposal.

Output

Output a single integer on one line: the minimal number of key uses in order to detune the piano.

Constraints and subtasks

The following constraints hold for all subtasks:
  • 1 ≤ n ≤ 105, the number of strings;
  • 2 ≤ fi ≤ 108, the original frequencies (but you may use the keys to go past those limits).
For the subtasks, we have the following additional constraints:
  • Subtask A (5 pts): The key is Nimbus440, and n ≤ 3.
  • Subtask B (10 pts): The key is Nimbus440, and n ≤ 15.
  • Subtask C (15 pts): The key is Nimbus440, and the original frequencies fi are all distinct.
  • Subtask D (30 pts): The key is Nimbus440.
  • Subtask E (40 pts): The key is XorOne.

Examples

Input:
4
2 2 4 4
Nimbus440

Output:
2
Input:
2
7 2
Nimbus440

Output:
0
Input:
4
2 4 6 10
XorOne

Output:
2



Added by:vlecomte
Date:2017-07-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Belgian IOI Selection Contest 2017