Trong một khu di tích cổ có N phòng đá được nối với nhau bởi các đường hầm. Hệ thống đường hầm có cấu trúc đặc biệt: giữa hai phòng đá bất kỳ luôn tồn tại đúng một đường đi đơn.

Ba cột năng lượng được đặt tại ba phòng đá khác nhau. Khi cả ba cột cùng được kích hoạt, toàn bộ các phòng và đường hầm nằm trên những đường đi cần thiết để kết nối ba phòng đó sẽ phát sáng.

Nói cách khác, với ba phòng đá khác nhau a, b, c, khu vực phát sáng là đồ thị con liên thông nhỏ nhất chứa cả ba phòng.

Để tránh quá tải, hệ thống chỉ hoạt động ổn định khi số phòng trong khu vực phát sáng đúng bằng D.

Hai cách kích hoạt được xem là khác nhau nếu bộ ba phòng được chọn khác nhau.

Với mỗi khu di tích, hãy đếm số bộ ba phòng khác nhau a < b < c sao cho đồ thị con liên thông nhỏ nhất chứa cả ba phòng có đúng D đỉnh.

Input

Dòng đầu tiên chứa số nguyên T — số lượng bộ test.

Mỗi bộ test gồm:

• Dòng đầu tiên chứa hai số nguyên N và D
  \((3 \le D \le N \le 2000)\).
• N - 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v
  \((1 \le u, v \le N,\ u \ne v)\), cho biết có một đường hầm nối trực tiếp hai phòng u và v.

Dữ liệu đảm bảo hệ thống đường hầm của mỗi bộ test là một cây.

Tổng N của tất cả các bộ test không vượt quá 2000.

Output

Với mỗi bộ test, in ra một số nguyên — số bộ ba phòng a < b < c sao cho đồ thị con liên thông nhỏ nhất chứa cả ba phòng có đúng D đỉnh.

Example

3
4 3
1 2
3 1
4 1
5 5
1 2
2 4
2 3
5 1
7 7
1 2
1 3
2 4
2 5
3 6
3 7

 3
 1
 0