In the network G(s, t, N, A, U)(s: the souce node, t: the sink node, N: the set of the nodes, A: the set of the arcs, U: the set of the capacity of the arcs), adding a arc's capacity with one unit may make the maximum flow larger. We call this arc as the adding-the-maximum-flow arc.
Now the problem is that giving a network G, you must calculate the number of the the adding-the-maximum-flow arcs in the network G.
Input
The first line of the input contains an integer T, giving the number of the test cases.
For each test case: The first line contains four integers: n, m, s and t(0 < n <= 400, 0 < m <= 10000, 0 < s, t <= n), giving the number of nodes, the number of arcs, the source node and the sink node.
And there are m lines followed: each line describe an arc: a, b, c, the arc is from a to b and its capacity is c(0 < a, b <= n, 0 < c < 1000).
Output
For each test case, the output contains a single integer which is the number of the adding-the-maximum flow arcs.
sample input
1
4 4 1 4
1 2 3
1 3 5
2 4 2
3 4 6
sample output
2
hint
There may be multiarcs in the network, that is to say there may be more than one arc between two nodes.