Cansado de la vida en su isla, Sora decidió viajar por diferentes partes del mundo en busca de oportunidades, y qué mejor forma de hacerlo que volar.

Un aeropuerto tiene una red de vuelo que cubre ~N~ puntos en el cielo conectados por ~M~ vuelos bidireccionales; es posible viajar desde un punto a cualquier otro, pero la red no está saturada (existe al menos un par de puntos que no tienen un vuelo directo entre sí). Debido a los fuertes vientos, y para evitar colisiones entre los aviones, se han impuesto restricciones a los vuelos por lo que es posible saber, para cada uno, cuánto tiempo ~W_j~ demorará un avión en llegar del punto ~U_j~ al punto ~V_j~ para cada ~j~ tal que ~1\le j\le M~.

Sora realizará ~T~ viajes, en cada viaje tomará un avión en un aeropuerto distinto, y su objetivo para cada viaje es comenzar desde el punto ~A~ y llegar al punto ~B~. Los aviones siempre viajan de un punto a otro por la ruta que menos tiempo consuma.

Sora considera que un viaje es óptimo si demora ~K~ unidades de tiempo completarlo, por lo que usando sus conocimientos en programación ha decidido añadir un vuelo extra a la red. Sin embargo esto no es tan fácil, ya que si no se hace con cuidado podría provocar un accidente. Para la red existente se considera seguro añadir un vuelo ~(U,V,W)~ si cumple con las siguientes condiciones:

1. No existe ningún vuelo entre los puntos ~U~ y ~V~.
2. El tiempo ~W~ del vuelo está en el rango ~[L,R]~.

Sora quiere saber cuántos vuelos seguros diferentes existen tal que si los añadiera a la red su viaje fuera óptimo; sin embargo, a pesar de poder hacerlo, prefirió dejarles este problema a sus amigos de la isla a modo de entrenamiento para la OII y de regalo de despedida.

Un vuelo se considera diferente de otro si difiere en los puntos que conecta o su tiempo.

Entrada

La primera línea contiene un entero ~T~ ~-~ la cantidad de viajes.

A continuación se describe el formato de cada viaje:

• La primera línea contiene tres enteros, ~N~, ~M~, ~K~ ~-~ la cantidad de puntos, la cantidad de vuelos y el tiempo óptimo, respectivamente.
• La segunda línea contiene dos enteros ~A~ y ~B~ ~-~ los puntos de inicio y fin del viaje, respectivamente.
• La tercera línea contiene dos enteros ~L~ y ~R~ ~-~ el rango de unidades de tiempo que puede tener el vuelo a agregar.
• Le siguen ~M~ líneas cada una con tres enteros ~U_j~, ~V_j~, ~W_j~ ~-~ la información de cada vuelo: los dos puntos que conecta y el tiempo que demora un avión al viajar entre ellos, respectivamente.

Salida

La salida debe contener ~T~ líneas ~-~ la ~i-~ésima de esas líneas debe contener la cantidad de vuelos seguros diferentes que se pueden agregar para que el ~i-~ésimo viaje sea óptimo.

Restricciones

• ~1\le T \le 4\cdot 10^4~
• ~3 \le N\le 10^5~
• ~1\le M\le 2\cdot 10^5~
• ~1\le K\le 10^{14}~
• ~1\le A,B\le N~
• ~1\le L\le R\le 10^9~
• ~1\le U_j,V_j\le N~
• ~1\le W_j\le 10^9~
• ~\sum N \le 10^5~
• ~\sum M \le 2\cdot 10^5~

Subtareas

Sea ~\delta(u, v)~ el tiempo mínimo de vuelo entre los puntos ~u~ y ~v~.

Subtarea	Restricciones Adicionales	Puntos	Dependencias
~1~	~M = N - 1~; El punto ~i~ está conectado al punto ~i+1~ para cada ~i~ tal que ~1\le i < N~; ~\sum N \le 5000~	~6~	~-~
~2~	~\sum N \le 50~; ~\sum R-L+1 \le 100~	~7~	~-~
~3~	~K < \delta(A, B)~; ~W_j = 2~ para cada ~j~ tal que ~1\le j\le M~; ~L = R~	~12~	~-~
~4~	~\sum N \le 5000~	~17~	~1-2~
~5~	~K < \delta(A, B)~; ~2\le W_j\le 10^9~ para cada ~j~ tal que ~1\le j\le M~	~24~	~3~
~6~	~-~	~34~	~1-5~

Ejemplos

Entrada 1

3
6 9 6
1 2
2 6
4 6 3
1 6 1
5 1 1
4 3 2
3 5 8
5 2 6
2 6 6
1 3 4
6 5 7
3 2 1
3 2
1 2
3 2 1
3 1 2
4 4 2024
2 4
2023 2024
2 3 2021
2 1 2022
4 1 1
4 3 2

Salida 1

3
2
0

En el primer viaje se pueden añadir los vuelos:

• ~(1,2,6)~
• ~(4,2,2)~
• ~(3,2,2)~

En el segundo viaje se pueden añadir los vuelos:

• ~(1,2,1)~
• ~(1,2,2)~

En el tercer viaje no hay forma de hacer que ~\delta(2,4) = 2024~