终于活成了自己讨厌的样子。

栗子米从来不知道，友谊的巨轮是单向的，直到有一天他和她在了一起。

这个地球上一共有n个人，他们之间会互相发消息。在每个时刻，a与b之间互相发了c条消息。对于每个人，它友谊的巨轮为最近m个时刻里与它发消息最多的人，如果有多个发消息最多的人，那么巨轮为这里面最近发的人。如果这个人在最近m个时刻里面没有与任何人发过消息，那么它没有友谊的巨轮。
在这个题目里面，我们设定一个时刻只有某两个人之间互相发了c条消息。
栗子米获得了上帝视角，她知道了每个时刻哪两个人发了消息。她经常会发现Alice和Bob发完晚安之后，又和Charlie聊一整晚。Bob的巨轮是Alice，但是Alice的巨轮却是Charlie。栗子米想知道，每个时刻发完消息之后，有多少的人的巨轮是单向的，即它的巨轮的巨轮不是它。

第一行一个整数T(T≤ 10)，表示数据组数。
每组数据第一行三个整数，表示n,k,m(1≤ n,k,m≤ 105)，表示总人数，总的时刻数，以及巨轮要求的是最近m个时刻。
接下来k行，每行三个正整数a,b,c(1≤ a,b≤ n,1≤ c≤ 109, a ≠ b)。

对于每组数据输出k行，表示每个时刻多少个人的巨轮是单向的。

1
5 7 5
1 2 1
1 3 1
2 4 1
1 2 2
4 5 2
3 4 2
1 5 1

0
1
0
2
1
1
1