Cặp số hữu tỉ \(p\) và \(q\) được cho là thân thiết nếu tồn tại số nguyên \(k\) sao cho \(p^k + q^k = 1\).

Ví dụ: \(1/4\) và \(3/4\) là một cặp số hữu tỉ thân thiết với \(k = 1\); \(5/3\) và \(5/4\) là một cặp số hữu tỉ thân thiết với \(k = -2\).

Bài toán đặt ra là với một dãy gồm \(N\) số hữu tỉ, tìm số lượng cặp số hữu tỉ thân thiết trong dãy.

Ghi chú: Cặp {a, b} và {b, a} được coi là một.

Đầu vào

Dòng đầu là số tự nhiên \(N\) \((2 \le N \le 10^5)\).

\(N\) dòng tiếp theo mỗi dòng gồm hai số nguyên dương \(n\) (numerator) và \(d\) (denominator) \((1 \le n, d \le 30)\) lần lượt là tử số và mẫu số của số hữu tỉ.

Đầu ra

Một số tự nhiên duy nhất là số cặp số hữu tỉ thân thiết trong dãy.

Ví dụ

Đầu vào 1:

5
4 1
4 3
3 5
8 10
4 5

Đầu ra 1:

3

Giải thích: 3 cặp thân thiết: {số thứ \(1\), số thứ \(2\)} \((k = -1)\); {số thứ \(3\), số thứ \(4\)} \((k = 2)\); {số thứ \(3\), số thứ \(5\)} \((k = 2)\).

Đầu vào 2:

4
3 4
1 4
2 8
3 4

Đầu ra 2:

4

Giải thích: \(4\) cặp thân thiết: {số thứ \(1\), số thứ \(2\)} \((k = 1)\); {số thứ \(1\), số thứ \(3\)} \((k = 1)\); {số thứ \(2\), số thứ \(4\)} \((k = 1)\); {số thứ \(3\), số thứ \(4\)} \((k = 1)\).