Cow el Nerd cree que a todo el mundo le gusta la matemática, así que le dio a Cherry Bomb dos arreglos de enteros: \(a\) y \(b\).

Dos arreglos de enteros \(a\) y \(b\), ambos de tamaño \(n\), son complementarios si existe un entero \(x\) tal que \(a_i + b_i = x\) para todo \(1 \le i \le n\). Por ejemplo, los arreglos \(a = [2, 1, 4]\) y \(b = [3, 4, 1]\) son complementarios porque \(a_i + b_i = 5\) para cada posición. En cambio, los arreglos \(a = [1, 3]\) y \(b = [2, 1]\) no lo son.

Se sabe que tanto \(a\) como \(b\) contienen \(n\) enteros no negativos, cada uno no mayor que \(k\). Desafortunadamente, Cherry Bomb ha perdido algunos elementos de \(b\). Los elementos perdidos están representados por \(-1\).

Ayuda a Cherry Bomb a contar cuántos arreglos \(b\) posibles puede completar de forma que \(a\) y \(b\) sean complementarios, reemplazando los \(-1\) por enteros no negativos no mayores que \(k\).

Entrada

La primera línea contiene un entero \(t\) (\(1 \le t \le 10^4\)): el número de casos de prueba.

Cada caso de prueba contiene:

1. Una línea con dos enteros \(n\) y \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(0 \le k \le 10^9\)): el tamaño de los arreglos y el valor máximo posible de sus elementos.
2. Una línea con \(n\) enteros \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le k\)).
3. Una línea con \(n\) enteros \(b_1, b_2, \dots, b_n\) (\(-1 \le b_i \le k\)). Si \(b_i = -1\), entonces el elemento está perdido.

Se garantiza que la suma de \(n\) en todos los casos de prueba no excede \(2 \cdot 10^5\).

Salida

Para cada caso de prueba, imprime exactamente un entero: el número de formas en que Cherry Bomb puede completar los elementos perdidos en \(b\) de modo que los arreglos \(a\) y \(b\) sean complementarios.

Ejemplos

Explicación

• En el primer ejemplo, la única manera de completar \(b\) para que sea complementario con \(a\) es \(b = [2, 0, 1]\).
• En el segundo caso, no existe ninguna forma de completar los valores perdidos de \(b\) para que cumplan la condición.
• En el cuarto ejemplo, algunos arreglos \(b\) que son complementarios con \(a\) incluyen: \([4, 2, 3, 0, 1]\), \([7, 5, 6, 3, 4]\) y \([9, 7, 8, 5, 6]\).