You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

Imagine you’re organizing a large event where people bring a variety of snack packs with different weights. You want to create unique “snack combos” by pairing up these packs in a way that satisfies a special rule:

You are given an array \(A\) of \(N\) positive integers representing the weights of each snack pack. Your task is to count the number of pairs (i,j) such that:

• \(1 <= i < j <= N\)
• The product \(A[i]×A[j]\) is divisible by the sum \(A[i]+A[j]\).

Input

The first line contains a single integer \(N\) \(( 2 ≤ 𝑁 ≤ 10^3 )\) — the number of snack packs.
The second line contains N space-separated integers \(𝐴[1] , 𝐴[2] , . . . , 𝐴[n] (1 <= A[i] <= 10^6 )\) — the weights of each snack pack.

Output

Print a single integer — the number of pairs \((i,j)\) that satisfy the conditions above.

Sample

5

2 3 4 6 12

3

Note

We need to check all pairs (i,j) such that 1<= i<j<=5 and verify if A[i]×A[j] is divisible by A[i]+A[j].

Pair (1, 2): A[1]=2, A[2]=3
* Product: 2×3 = 6
* Sum: 2+3 = 5
* 6 mod  5 ≠ 0 (not valid)
Pair (1, 3): A[1]=2, A[3]=4
* Product: 2×4 = 8
* Sum: 2+4 = 6
* 8 mod  6 ≠ 0 (not valid)
Pair (2, 4): A[2]=3, A[4]=6
* Product: 3×6 = 18
* Sum: 3+6 = 9
* 18 mod  9 = 0 (valid)