Problema B - Teoria de (Quase) Tudo

O físico António prepara-se para mais um dia de trabalho no seu laboratório de partículas. Desde bosões a fermiões, o que não faltam são partículas para estudar! O objetivo do António para hoje é estudar a estabilidade de partículas, ou seja, que partículas é que não vão decair para outras.

No laboratório ele tem exatamente C conjuntos de N partículas seguidas numa linha cada um. Para identificar o tipo de partícula (se é um neutrino muónico ou um gluão, por exemplo), a cada partícula i de cada conjunto é atribuído um inteiro positivo p_i. Um par de partículas de igual valor é considerado estável se todas as partículas entre eles têm um valor que não dista mais do que D em relação ao par. Formalmente, duas partículas nas posições i e j formam um par estável se p_i=p_j e |p_k-p_i|≤D para qualquer k respeitando i<k<j .

António está mesmo interessado em conhecer a quantidade de pares de partículas que são estáveis em cada conjunto. Vamos ver um exemplo. Considera que existe um conjunto com as seguintes N = 6 partículas:

Além disso sabe-se que D = 1 para este conjunto. Neste caso há 4 pares de partículas iguais, dos quais apenas 1 é estável. São eles:

• Pares não estáveis:
  • Posições 1 e 3 (ambas com valor 1): entre elas há apenas uma partícula de valor 4, que não está a distância D (|4-1|=3 > 1).
  • Posições 1 e 5 (ambas com valor 1): entre elas há 4, um 2 e um 1. Destas, a partícula de p = 4 não está a distância de D (|4-1|=3 > 1).
  • Posições 2 e 6 (ambas com valor 4): elas entre há um 1, um 2 e outro 1. Destas nenhuma está à distância de D (|1-4|=3 > 1 e |2-4|=2 > 1).
• Pares estáveis:
  • Posições 3 e 5 (ambas com valor 1): entre elas há apenas uma partícula de valor 2, que está à distância necessária (|2-1|=1 ≤ 1).

O António rapidamente usou a equação de Dirac e a regra de ouro de Fermi para calcular quantos pares de partículas são estáveis por conjunto. Agora é a tua vez de calcular a resposta, mostra que a Ciência de Computadores não é inferior à Física ou o António irá gozar contigo para sempre!

O Problema

Dados C conjuntos de N partículas e os seus respetivos valores, a tua tarefa é calcular, para cada conjunto, a quantidade de pares de partículas do mesmo valor que são estáveis, isto é, cujos valores das partículas entre elas estão no máximo à distância D do valor do par.

Input

Na primeira linha vem um inteiro C que representa o número de conjuntos.

Seguem-se C conjuntos de partículas. Cada conjunto começa com uma linha com dois números inteiros N e D, representando o número de partículas e a distância máxima para garantir estabilidade. Seguem-se N inteiros onde o i-ésimo representa o valor de p_i.

Output

O output contém C inteiros que representam o número de pares estáveis por conjunto. Estes números serão inferiores a 2⁶³.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 35% dos pontos, N ≤ 200.

Para um conjunto de casos de teste valendo 65% dos pontos, N ≤ 5 000.

Exemplo de Input 1

2
6 1
1 4 1 2 1 4
10 2
1 3 5 1 2 3 5 1 2 3

Exemplo de Output 1

1
3

Exemplo de Input 2

2
6 2
1 4 1 2 1 4
8 1
1 2 1 2 1 2 1 2

Exemplo de Output 2

1
12