405240: GYM101856 D Dream Team

Before the World Cup, we would like to form the ultimate dream team. The team that will win against all teams. We have a big group of the top N players in the world, where each player has a number representing his skill level. Two players i and j with skill levels a_i and a_j have a compatibility of passing the ball between each other; this compatibility level is measured by the greatest common divisor of their skill levels (i.e. compatibility(i, j) = gcd(a_i, a_j)). We would like to decide a strategy that connects all the players of the dream team with a tree of connections between the players. If two players are directly connected in the chosen strategy, then they will pass the ball between each others during the matches, with the compatibility level between them. The compatibility of the strategy is the sum of the compatibility levels of its connections. What is the maximum total compatibility of the chosen strategy that connects all players?

The first line of the input contains a single integer 1 ≤ T ≤ 50 the number of test cases. Each test case consists of one line that contains N + 1 space separated integers; the first integer is N, followed by the skill levels a₁, ..., a_n; where 1 ≤ N ≤ 10⁵ and 1 ≤ a_i ≤ 10⁵ for all i.

For each test case, print a single line displaying the case number and the maximum compatibility of the dream team's strategy.

2
2 3 6
5 5 6 7 10 21

Case 1: 3
Case 2: 17

In the second test case we connect the players 3 - 5 with compatibility 7, players 1 - 4 with compatibility 5, players 2 - 5 with compatibility 3 and players 2 - 4 with compatibility 2; therefore the total compatibility of the dream team's strategy is 17.