Slices That Make a Whole Pie

A bakery sells leftover pie by the fraction. Leftover i is slices[i] = [num, den], meaning num / den of a pie, with 0 < num < den. The same amount may be written in different ways ([1, 2] and [3, 6] are both half a pie). Return the number of index pairs (i, j) with i < j whose two leftovers add up to exactly one whole pie.

Examples

Input:  slices = [[1, 3], [2, 3], [4, 6], [1, 2], [5, 10]]
Output: 3
Explanation: 1/3 pairs with 2/3 and with 4/6; 1/2 pairs with 5/10.

Input:  slices = [[1, 4], [1, 4]]
Output: 0

Constraints

• 0 <= len(slices) <= 5 * 10**4
• 1 <= num < den <= 10**9
• Target complexity: O(n log D) time, where D is the largest denominator.

Goals

• Reduce every fraction to one canonical key
• Look up the complement 1 - p/q in the table
• Count each pair once, including fractions equal to their own complement