Once upon a time there lived a king in a far far country. In the country, there are n cities and m roads. He was severely attacked by his enemy. The enemy damaged all the cities of King's country. As the roads between the cities had been damaged, the King wanted to repair those. So he decided to launch a tender for this.

As King's country is a well managed country. By well managed country, we mean that it is possible to go from each city to any other city. But now as the city has been destroyed by enemies, all the roads are broken, the king will like to rebuild the roads in such a way that it is still a well manged country.

Cost of repairing the road in the country is really weird, it is not addition of costs but it is instead multiplication of those. What it means that if the king decides that he should repair 5 roads, then total cost of repairing those roads will be multiplication of all the 5 costs.

As the King's treasure has been damaged by the attack of foreign city, he would like to spend minimum amount of money and that the will want that his country still remains well managed country. Surprisingly the company that was given tender had a rule that all the costs will be in powers of two, as they were really love with binary numbers.

As value of the total cost can be really large. We do not want to know the actual cost, instead output number of divisors of the number.

Input

T: number of test cases (T <= 5)

n and m (n <= 10^5, m <= 2 * 10^5)

Next m lines will have a, b, c, which denotes that cities a and b are connected with road of cost c.

(2 <= c <= 10^18, and c will always be power of 2) (1 <= a <= n) (1 <= b <= n)

Output

For each test case, output a single line containing a number as stated in the problem.

Example

Input:
4
2 1
1 2 16
3 2
2 3 32
1 2 16
3 3
2 3 32
1 2 16
1 3 64
5 5
1 2 2
2 3 2
1 3 4
3 4 16
3 5 8

Output:
5
10
10
10