Có \(N\) điểm trong không gian \(D\) chiều.

Tọa độ của điểm thứ \(i\) là \((X_{i1}, X_{i2}, ..., X_{iD})\).

Khoảng cách giữa hai điểm có tọa độ \((y_1, y_2, ..., y_D)\) và \((z_1, z_2, ..., z_D)\) là \((y_1 - z_1)^2 + (y_2 - z_2)^2 + ... + (y_D - z_D)^2\).

Hỏi có bao nhiêu cặp \((i, j)\) (\(i<j\)) sao cho khoảng cách giữa điểm thứ \(i\) và điểm thứ \(j\) là một số nguyên?

Ràng buộc:

• Tất cả giá trị đầu vào là số nguyên.
• \(2 \leq N \leq 10\)
• \(1 \leq D \leq 10\)
• \(-20 \leq X_{ij} \leq 20\)
• Không có hai điểm nào có tọa độ giống nhau. Nghĩa là nếu \(i eq j\), tồn tại \(k\) sao cho \(X_{ik} eq X_{jk}\).

ĐỊNH DẠNG ĐẦU VÀO

Đầu vào được cung cấp từ đầu vào chuẩn như sau:

N
D
X_{11} X_{12} ... X_{1D}
X_{21} X_{22} ... X_{2D}
...
X_{N1} X_{N2} ... X_{ND}

ĐỊNH DẠNG ĐẦU RA

In ra số lượng cặp \((i, j)\) (i<j) sao cho khoảng cách giữa điểm thứ \(i\) và điểm thứ \(j\) là một số nguyên.

Ví dụ:

Input

3 2
1 2
5 5
-2 8

Output

1

Số cặp có khoảng cách là số nguyên là một, như sau:

Khoảng cách giữa điểm thứ nhất và điểm thứ hai là \(|(1-5)|^2 + |(2-5)|^2 = 5\), là một số nguyên. Khoảng cách giữa điểm thứ hai và điểm thứ ba là \(|(5+2)|^2 + |(5-8)|^2 = 58\), không phải là số nguyên. Khoảng cách giữa điểm thứ ba và điểm thứ nhất là \(|(-2-1)|^2 + |(8-2)|^2 = 35\), không phải là số nguyên.

Input

3 4
-3 7 8 2
-12 1 10 2
-2 8 9 3

Output

2

Giải thích ví dụ mẫu:

• Ví dụ 1:

  • Có một cặp điểm có khoảng cách là số nguyên: (1, 2) và (5, 5) với khoảng cách là 5.

• Ví dụ 2:

  • Có hai cặp điểm có khoảng cách là số nguyên:
    1. (−3, 7, 8, 2) và (−12, 1, 10, 2) với khoảng cách là 268.
    2. (−12, 1, 10, 2) và (−2, 8, 9, 3) với khoảng cách là 118.
       

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House