IITKWPCG  Help the old King
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 severly 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 wierd, 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.
(c >= 2 && c <= 10^18 && c will always be power of 2) (1 <= a <= n) and (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
hide comments
marethyu1:
20190527 20:05:53
Utilized __builtin_ctzll! 

kaushalag29:
20180630 12:04:17
"all the costs will be in powers of two" this line helped a lot. 

be1035016:
20180630 09:13:14
enjoyed solving it:) 

ANAND:
20160903 16:27:23
pls check my solution id 17641731 . Last edit: 20160903 16:39:36 

BA_AK:
20140128 17:43:49
Top of the table \0/ !! 

Chandan Mittal:
20140124 00:01:58
Simple yet Classical :) 
Added by:  praveen123 
Date:  20130805 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 