Bạn được cho một dãy số nguyên dương a₁, a₂, ..., a_n. Đếm số cặp (i, j) thỏa mãn:

• 1 ≤ i < j ≤ n
• a_i + a_j chia hết cho 9

Input

• Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 10⁶).
• Dòng thứ hai chứa n số nguyên dương a_i (|a_i| ≤ 10⁹).

Output

In ra số lượng cặp thỏa mãn điều kiện.

Scoring

• 50% số điểm: n ≤ 5000.
• 50% còn lại: không có giới hạn gì thêm.

Example

Input:
5
3 5 3 6 4

Output:
3

Giải thích

Các cặp thỏa mãn là: (1, 4), (2, 5), (3, 4).