Planet Gozz calls for aid! They are under attack from the minions of the evil MAX! Gozz has sent out messages to other planets using an FTL email system so all planets receive the message at the same time, but due to some wacky timespace hijinks the receipt time may be years after the send time, or even years before. None of the planets that receive the message have FTL travel, but they do have access to wormholes that allow instantaneous travel through time and space.

A wormhole \(w\) allows travel from a planet \(s_w\) to a planet \(e_w\). Travelling through a wormhole \(w\) sends the traveller through time by a fixed number of years \(t_w\) which can be positive (travelling forwards in time) or negative (travelling backwards in time). All wormholes are one-way (you should know this). The message travels \(M\) years before being received at the same time by all planets (i.e. the message is sent at year 0 and arrives everywhere at year \(M\)). All planets (except planet Gozz) are guaranteed to have a path of wormholes to planet Gozz. It's impossible to travel from a planet to itself (via other planets) in negative time (that would just be ridiculous). How many planets can arrive at planet Gozz by the time of the attack (year 0)?

Input Specification

The first line contains an integer \(T\), the number of test cases to follow. Each test case begins with a line containing three space-separated integers \(N,M,P\), where \(N\) is the number of wormholes, \(M\) is the receipt time of the message in years, and \(P\) is the number of planets. Following this in each test case is \(N\) lines. The \(w\)th line describes a single wormhole \(w\) and is specified by three space-separated integers \(s_w,e_w,t_w\), where \(0 \leq s_w,e_w \leq P-1\) are the source and destination planet indexes of the wormhole, respectively, and \(t_w\) is the time travelled in years when passing through the wormhole.

Planet Gozz is always at index 0. For any ordered pair of planets \(s,e\) at most one wormhole exists from \(s\) to \(e\). There is never a wormhole from a planet to itself.

Output Specification

For each test case, output a single line containing the number of planets that can arrive at planet Gozz (index 0) at or before the year the message was sent (year 0) (not including planet Gozz itself).

Bounds

Note this problem includes sub-problems of increasing difficulty worth different numbers of points:

• 30 points: \(N = P-1\) and \(-1000 \leq t_w \leq 1000\)
• 10 points: \(N \leq P^2-P\) and \(1 \leq t_w \leq 1000\)
• 60 points: \(N \leq P^2-P\) and \(-1000 \leq t_w \leq 1000\)

For all sub-problems:

\(1 \leq T \leq 10\)

\(-10^5 \leq M \leq 10^5\)

\(2 \leq P \leq 100\)

Sample Input

1
6 1 4
1 0 -2
2 0 -1
3 1 2
1 2 4
3 2 3
2 1 5

Sample Output

2

In the sample test case each planet receives the message in year 1. The shortest path to planet Gozz (planet 0) from planet 1 would take -2 years (1 to 0, arriving in year -1), from planet 2 would take -1 years (2 to 0, arriving in year 0), and from planet 3 would take 0 years (3 to 1 to 0, arriving in year 1). Thus only planets 1 and 2 can arrive by year 0, and the total number is 2. Other paths exist but they would take longer.