Before the celebration of the Day of the programmer, the office of the IT company was decorated with a sequence of numbers of length N, a = {a1, a2, a3, ..., aN}. Bugs Hunter, a member of the testing department, would like to play around with this sequence. In particular, he would like to repeat the following operation as many times as possible.
For every i that satisfies 1<=i<=N, do one of the following: "divide ai by 2" and "multiply ai by 3". You can't do "multiply ai by 3" immediately for each i during one operation, the value of ai after any action must be an integer.
Bugs Hunter does one operation in 1 second, regardless of the number of numbers in the sequence. Determine the maximum time after which Bugs Hunter will return to his work?
Input
The first line contains an integer N (1<=N<=10000). The second line contains N integers ai (1<=ai<=10
9).
Imprint
Print one number - the maximum number of seconds after which Bugs Hunter will return to his job.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3
5 2 4
| 3 |
The sequence is originally 5,2,4.
Three operations can be performed as follows:
- first multiply a1 by 3, multiply a2 by 3 and divide a3 by 2. Now the sequence is 15,6,2;
- then multiply a1 by 3, divide a2 by 2 and multiply a3 by 3. Now the sequence is 45,3,6;
- finally multiply a1 by 3, multiply a2 by 3 and divide a3 by 2. Now the sequence is 135,9,3.
Further, with each number, you can only perform multiplication by 3, but this action is not allowed for all numbers ai at once.
So the answer is 3. |
| 2 |
4
631 577 243 199
| 0 |
|
| 3 |
10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776 |
39 |
|