Description

There are n children in Johnny Johnny' s family.

And number i child wants to have a_i units of sugar.

But their PaPa don't want them eat too much sugar. Therefore he will randomly choose some children and only give them the great common divisor of a_i. 

 

For example, if there're n=5 children and a_i = { 1, 4, 6, 7, 18 }.

Suppose PaPa choose the children numbered 2,3,5.

Then all children will only get  gcd(a₂, a₃, a₅) = gcd(4,6,18) = 2 unit of sugar.

 

Now Johnny wants to know what's the maximum amount of sugar they can get.(PaPa will at least choose two child) 

If you can help him, he will laugh at you for you don't have any sugar " Ha Ha Ha!!! "

 

To calculate great common divisor, you can use the method 輾轉相除法(https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)

Input

input contains two lines.

First line only contains one integer n ( 2 <= n <=  1000)

Second line contain n integers a₁ ~ a_n ( 1<= a_i <= 1000 )

Output

output contains only one integer the maximum amount of sugar they can get.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Long long long long long long long long long long time ago, there's a lovely kingdom named "Chess". There's King, Queen, Knight, Castle, Bishop, ...etc. Just like the modern game "chess". 

A king definitely have not only one castle or knight. But no one says that a king shouldn't have two or more queens (same as queen, a queen is able to have two or more kings). Now in this kingdom, the king has N queens. 

However, all the queens want to get the title "King's favorite", if one is uglier than the other one (which is judged by the king), then just win by manner. If one is more rude than the other one, then just win by skills. But if a queen loses on everything...... then just let them disappear or die "accidentally"...HEHEHE..... The king soon realized that, for the safety of all of his lovely queens, he must make them cannot see each other. 

Now, the king ask you, the mighty programming knight, for a mission. They want to find out how many possibilities that the queens won't launch a war in the palace.

---

• There are N queens in the palace.
• The palace is just like a chessboard with size N*N. 
• Queen can see all people in 8 directions(←, ↑, →, ↓, ↖, ↗, ↘, and ↙. Just like what queen in the chess does). If any queen see other queens, the mission will fail. 
• Find out the total amount of states that all queens are placed in the palace and mission isn't fail.

Warning! Do not just look up the answer table! You are supposed to solve this problem by recursive. Otherwise you will regret it!

Input

The input contains exactly one number N. 

1 <= N <= 14.

Output

Output only one number ── the total amount of states that queens are placed in the palace and mission isn't failed.

Remember to print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss