Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

I’ve read many problems in my ICPC career, sometimes the meaning of a problem often makes me confused.

When I read a problem more than three times and still can’t get the idea what is the problem saying about, I may become like this

or

I hope you won’t be the above person after you read this problem.

Mr. Zstu and Mr. Hdu get a set of numbers {$A_{1}, A_{2}, ... , A_{n}$}, they have different opinions about the beautiful value of the set.

Mr. Zstu defines the beautiful value like this:

Make the set become a sequence, the beautiful value of the sequence is the sum of all the interval’s gcd(greatest common divisor), and the beautiful value of the set is the sum of the beautiful value of all the possible sequence. For example, set{$1,2,3$} can be six different sequence {$1,2,3$},{$1,3,2$},{$2,1,3$},{$2,3,1$},{$3,1,2$},{$3,2,1$}.

Mr. Hdu defines the beautiful value like this:

For k from 1 to n, choose k numbers of the set, and calculate the gcd of the k numbers. The beautiful value of the k numbers is k * (gcd of the k chosen numbers). The beautiful value of the set is the sum of all of the beautiful value of k numbers.

Which beautiful value is larger, Mr. Zstu and Mr. Hdu invite the judge Mr. Xiasha to help.

Given that both of the value are too big, the stupid Mr. Xiasha mod both of the values by 258280327, so here is the question, which value is bigger after mod operation?

When I read a problem more than three times and still can’t get the idea what is the problem saying about, I may become like this

or

I hope you won’t be the above person after you read this problem.

Mr. Zstu and Mr. Hdu get a set of numbers {$A_{1}, A_{2}, ... , A_{n}$}, they have different opinions about the beautiful value of the set.

Mr. Zstu defines the beautiful value like this:

Make the set become a sequence, the beautiful value of the sequence is the sum of all the interval’s gcd(greatest common divisor), and the beautiful value of the set is the sum of the beautiful value of all the possible sequence. For example, set{$1,2,3$} can be six different sequence {$1,2,3$},{$1,3,2$},{$2,1,3$},{$2,3,1$},{$3,1,2$},{$3,2,1$}.

Mr. Hdu defines the beautiful value like this:

For k from 1 to n, choose k numbers of the set, and calculate the gcd of the k numbers. The beautiful value of the k numbers is k * (gcd of the k chosen numbers). The beautiful value of the set is the sum of all of the beautiful value of k numbers.

Which beautiful value is larger, Mr. Zstu and Mr. Hdu invite the judge Mr. Xiasha to help.

Given that both of the value are too big, the stupid Mr. Xiasha mod both of the values by 258280327, so here is the question, which value is bigger after mod operation?

There are multiple test cases.

Each test case begins with an integer n$(1 \leq n \leq 100000)$

The next line is n integers $A_{1},A_{2},...,A_{n}$

All of the integers are between 1 and 100000.

Each test case begins with an integer n$(1 \leq n \leq 100000)$

The next line is n integers $A_{1},A_{2},...,A_{n}$

All of the integers are between 1 and 100000.

提交代码