Two friends, Alisa and Yuki, planted a tree with nn vertices in their garden. A tree is an undirected graph without cycles, loops, or multiple edges. Each edge in this tree has a length of kk. Initially, vertex 11 is the root of the tree.
Alisa and Yuki are growing the tree not just for fun, they want to sell it. The cost of the tree is defined as the maximum distance from the root to a vertex among all vertices of the tree. The distance between two vertices uu and vv is the sum of the lengths of the edges on the path from uu to vv.
The girls took a course in gardening, so they know how to modify the tree. Alisa and Yuki can spend cc coins to shift the root of the tree to one of the neighbors of the current root. This operation can be performed any number of times (possibly zero). Note that the structure of the tree is left unchanged; the only change is which vertex is the root.
The friends want to sell the tree with the maximum profit. The profit is defined as the difference between the cost of the tree and the total cost of operations.
Help the girls and find the maximum profit they can get by applying operations to the tree any number of times (possibly zero).
Input
The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The description of the test cases follows.
The first line of each test case contains integers nn, kk, cc (2≤n≤2⋅1052≤n≤2⋅105; 1≤k,c≤1091≤k,c≤109) — the number of vertices in the tree, the length of each edge, and the cost of the operation.
The next n−1n−1 lines of the test case contain pairs of integers uiui, vivi (1≤ui,vi≤n1≤ui,vi≤n) — the edges of the graph. These edges form a tree.
The sum of the values of nn over all test cases does not exceed 2⋅1052⋅105.