Drum Loops That Never Line Up Early

A producer has drum loops; loop i is beats[i] beats long. Two loops started together first land on a common downbeat again after lcm(a, b) beats. A pair of loops is fresh if that does not happen before a * b beats, which is exactly when gcd(a, b) == 1.

Return the number of index pairs i < j whose loops are fresh. Loops with equal lengths are still different loops.

Examples

Input:  beats = [4, 6, 9, 5]
Output: 4
Explanation: (4, 9), (4, 5), (6, 5), (9, 5) are fresh; (4, 6) share 2 and (6, 9) share 3.

Input:  beats = [1, 1, 2, 2]
Output: 5
Explanation: every pair except (2, 2) is fresh; gcd(1, 1) = 1.

Constraints

• 0 <= len(beats) <= 10**5
• 1 <= beats[i] <= 10**5
• Checking all pairs with math.gcd is far too slow for the largest inputs.

Goals

• Count pairs by the value of their gcd instead of pair by pair
• Count how many values are multiples of each d with a harmonic-sum loop
• Peel off pairs whose gcd is a larger multiple, working from the top down