Tapas wants to gift his new girlfriend a special present on Valentines' Day. To absolutely impress his girlfriend he has decided to gift her a self composed song comprising of N notes. Each note is represented by a natural number. Melody of the song composed of N notes in the sequence P[1],P[2],P[3],...,P[N] is defined as summation of GCD(P[i],P[i+1]) where 1 <= i < N. Tapas has asked you to help him determine the maximum possible Melody in any possible sequence in which notes are played. All the notes should be used exactly once in the song.
Input: First line consists of a single integer N. Second line consists of N natural numbers denoting the notes.
Output: Determine the sequence in which the notes should be played to maximize the Melody and output this maximum possible Melody.
Constraints:
2<= N <= 15
P[i] <= 10^9
Explanation
Different possible orders are :
5 10 2, Melody = 7
5 2 10, Melody = 3
2 5 10, Melody = 6
2 10 5, Melody = 7
10 2 5, Melody = 3
10 5 2, Melody = 6
Maximum possible Melody is 7
