A city contains 3 types of roads (1, 2 and 3) which join the sectors of the city. Road type1 is used by two wheelers only, road type 2 is used by four wheelers only and road type 3 is used by both.

The mayor need to destroy some roads so as to reduce the expense on maintenance of roads. What is the maximum number of roads that can be destroyed such that the city will be still connected for both types of vehicle.

A connected city is one where it is possible to travel from any sector to any other using existing roads. All the roads are bidirectional.

Input

The first line will contain a single integer T, denoting the number of test cases. Each test case will consist of first, a line containing two integers N and M which denote the number of sectors and the number of roads. The next M lines will contain three space separated integers indicating the two sectors that are joined and the road type.

Output

A single integer, which denotes the maximum number of roads you can destroy.

Constraints

T in set [1, 10]

N in set [1, 100]

M in set [1, 10000]

Example

Input:
1
5 7
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
5 2 2
1 5 1

Output:
2