War in Treeland Again

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK108/hindi/WARTLND.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK108/mandarin/WARTLND.pdf), [Russian](http://www.codechef.com/download/translated/COOK108/russian/WARTLND.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK108/vietnamese/WARTLND.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK108/bengali/WARTLND.pdf) as well. There is a fullscale war taking place in Treeland. Chef needs to travel between cities in Treeland to work, but during the war, it is not safe. In Treeland, there are $N$ cities (numbered $1$ through $N$) and $N  1$ bidirectional roads connecting them in such a way that Chef can reach each city from any other city using these roads. Each road is occupied by a unique faction that assigned a positive integer code to it. Let $f(A, B)$ denote the greatest positive integer which divides the code of each road on the shortest path between cities $A$ and $B$ (the GCD of these codes). If Chef wants to go from city $A$ to city $B$ *safely*, he needs to pay $f(A, B)$ units of money. Since Chef is not sure between which pairs of cities he is going to travel, he wants to know $$S = \sum\limits_{i=1}^{N} \sum\limits_{j=i+1}^{N} f(i, j) \,.$$ Help Chef calculate $S$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  Each of the next $N1$ lines contains three spaceseparated integers $X$, $Y$ and $Z$ denoting that cities $X$ and $Y$ are connected by a road with code $Z$. ### Output For each test case, print a single line containing one integer $S$. ### Constraints  $1 \le T \le 10$  $1 \le N, Z \le 10^5$  $1 \le X, Y \le N$ ### Example Input ``` 1 5 1 2 4 1 3 3 2 4 1 2 5 2 ``` ### Example Output ``` 17 ``` ### Explanation **Example case 1:**  $f(1, 2) = \mathrm{GCD}\,(4) = 4$  $f(1, 3) = \mathrm{GCD}\,(3) = 3$  $f(1, 4) = \mathrm{GCD}\,(4, 1) = 1$  $f(1, 5) = \mathrm{GCD}\,(4, 2) = 2$  $f(2, 3) = \mathrm{GCD}\,(4, 3) = 1$  $f(2, 4) = \mathrm{GCD}\,(1) = 1$  $f(2, 5) = \mathrm{GCD}\,(2) = 2$  $f(3, 4) = \mathrm{GCD}\,(3, 4, 1) = 1$  $f(3, 5) = \mathrm{GCD}\,(3, 4, 2) = 1$  $f(4, 5) = \mathrm{GCD}\,(1, 2) = 1$Author:  ezio_26 
Editorial  https://discuss.codechef.com/problems/WARTLND 
Tags  cook108, divisors, ezio_26, inclusionexclusion, taran_1407, unionfind 
Date Added:  11072019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 