Aliens have designed a new ranking system for N cows in planet Mars. Cows near the bottom of the rankings list have become jealous of the top rankers, while the top rankers started looking down on their less successful cows.

The ranking system has 2 rules:

1. Two cows are friends if their ranks are close enough, more precisely, if they differ by at most K. For example, if K = 1, then only neighbouring cows on the rankings list are friends.
2. Two cows are good friends if they are friends and their names have the same length.

Find the number of pairs of cows which are good friends in Mars.

Input

The first line contains the number of testcases T (1 ≤ T ≤ 5). Followed by the descriptions of each test case.

Each test case contains two positive integers, N (3 ≤ N ≤ 300 000) and K (1 ≤ K ≤ N), from the problem statement.

Each of the following N lines contains a single cow's name. The names are given in the order they appear on the rankings list. They consist of between 2 and 20 (inclusive) uppercase English letters

Output

Print the required number of pairs of good friends.

Example

Input:
2
4 2
XVA
IWO
TNJ
TDM
6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

Output:
5
2