const int N = 2e5+3;
const lli MOD = 998244353;
vector<pair<lli, lli>> a(N);

void dfs(int node, int par, vector<tuple<int,lli,lli>> g[]) {
    
    lli p = a[node].first;
    lli q = a[node].second;
    
    for(auto [j,x,y] : g[node]) {
        if(j != par) {
            a[j].first = (p % MOD * y % MOD) % MOD;
            a[j].second = (q % MOD * x % MOD) % MOD;
        }
    }
    for(auto [j,x,y] : g[node]) {
        if(j != par) {
            dfs(j,node,g);
        }
    }
}

lli LCM(lli a, lli b) {
    return (a*b) / __gcd(a,b);
}
void solve(){ 
    
    int n;
    cin >> n;
    
    vector<tuple<int,lli,lli>> g[n+1];
    FOR(k,1,n-1) {
        int i,j,x,y;
        read(i,j,x,y);
        g[i].pb({j,x,y});
        g[j].pb({i,y,x});
    }
    
    a[1] = {1,1};
    dfs(1,0,g);
    
    lli lcm = 1 , ans = 0;
    FOR(i,2,n) {
        lcm = LCM(lcm, a[i].second);
        lcm %= MOD;
    }
    
    FOR(i,1,n) {
        ans += a[i].first * (lcm/a[i].second);
        ans %= MOD;
    }
    ans /= __gcd(ans,lcm);
    cout << ans << '\n';
    
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin>>t;
    while(t--)
    solve();
	
	return 0;
}

Joey and Chandler have plans to go to the Knicks game. However , Joey also wants to try sandwiches from different restaurants before going. He needs to return on time so that Chandler and he can leave for the game. All the N restaurants lie on the same street at positions p[i] and Joey spends time t[i] at the respective restaurants. Joey takes 1 unit of time to travel 1 unit on the path i.e. to travel from position 1 to 3 , he takes 3-1 = 2 units of time. Assuming that Joey starts from 0 , and Chandler and he have to leave for the game in T seconds , can you tell what is the maximum number of restaurants that Joey can cover before leaving.

EXAMPLE Consider N = 3 , T = 10 and pi , ti = [{1,3} , {2,3}]

• If Joey goes to the first restaurant the total time consumed is 1(to travel) + 3(spent at restaurant) = 4. Time remaining = 10-4 = 6.
• Now if he goes to second restaurant , time taken = (to travel from 1) + 2(spent here) = 3. Time remaining = 6 — 3 = 3.
• For returning from here time taken is 2units. Time remaining = 3-2=1.

So the answer is 2.

dp[i][0] -> If he chooses not to stay at the restaurant but travel through here , we only consider time to reach here i.e. p[i]

dp[i][1] -> If he chooses to stay here , we take time spent here into consideration i.e. t[i]

At each position we will take 2 cases : when he decides to stay at the restaurant and when he just passes through this position. At each point we will also check if the total time taken + time to return back is less than or equal to T. If not so we will break from here as we cannot go ahead from here. (I have already sorted according to position).

int dp[n+1][2] , T0 = 0, T1 = 0 , ans = 0;
    dp[1][0] = 0 , T0 = inp[1].first;
    
    if(2 * inp[1].first + inp[1].second <= T) {
        dp[1][1] = 1 , T1 = inp[1].first + inp[1].second , ans++;
    } else {
        dp[1][1] = 0 , T1 = inp[1].first;
    }
    
    
    for(int i=2; i<=n; i++) {
        dp[i][0] = dp[i][1] = 0;
        
        //dp[i][0]
        if(T0 + 2 * inp[i].first - inp[i-1].first <= T) {
            dp[i][0] = max(dp[i][0] , dp[i-1][0]);
            T0 = T0 + inp[i].first - inp[i-1].first;
        } 
        
        if(T1 + 2 * inp[i].first - inp[i-1].first <= T) {
            dp[i][0] = max(dp[i][0] , dp[i-1][1]);
            T0 = T1 + inp[i].first - inp[i-1].first;
        }
        
        //dp[i][1]
        if(T0 + 2 * inp[i].first - inp[i-1].first + inp[i].second <= T) {
            dp[i][1] = max(dp[i][1] , dp[i-1][0] + 1);
            T1 = T0 + inp[i].first - inp[i-1].first + inp[i].second;
        } 
        
        if(T1 + 2 * inp[i].first - inp[i-1].first + inp[i].second <= T) {
            dp[i][1] = max(dp[i][1] , dp[i-1][1] + 1) ;
            T1 += inp[i].first - inp[i-1].first + inp[i].second;
        }
        
        else break;
        ans = max({ans , dp[i][1] , dp[i][0]});
    }

const int MAXN = 1e5+1;
int sparse[MAXN][26];
void pre(int n , vi &a) {
    
    for(int i=0; i<n; i++) sparse[i][0] = a[i];
    
    for(int j=1; (1<<j) < n ; j++) {

        for(int i=0; (i + (1<<j) - 1) < n; i++) {

            sparse[i][j] = min (sparse[i][j-1] , sparse[i+(1<<j-1)][j-1]);

        }

    }
    
}

    int q;
    cin >> q;
    
    while(q--) {
        
        int l , r;
        cin >> l >> r;
        
        int j = r-l+1;
        int ans = INT_MAX;
        
        for(int i=0; i<32; i++) {
            if(j & (1<<i)) 
                ans = min(ans , sparse[l][i]);
        }
        
        cout << ans << "\n";
    }

#include <iostream>
#include <bits/stdc++.h>
using namespace std; 

#define MAX     1000
#define pb       push_back
#define ppb      pop_back
#define FOR(i,s,e)      for(int i=s; i<=e; i++) 
#define RFOR(i,s,e)     for(int i=e; i>=s; i--)
#define lli     long long int
#define mod       1000000007
#define ppc     __builtin_popcount
#define ppcll     __builtin_popcountll
#define gs      getline(cin, s);
#define c_yes   std::cout << "YES" << std::endl;
#define c_no   std::cout << "NO" << std::endl;
#define ALL(x)      x.begin() , x.end()
typedef   pair<int, int> pi;
typedef   std::vector<int> vi;
typedef   std::vector<vector<int>> vvi;
typedef   std::vector<lli> vlli;
typedef   std::vector<char> vc;
typedef   std::vector<string> vs;
typedef   std::vector<pi> vpi;
typedef   priority_queue<int> max_heap_int;
typedef   priority_queue<string> max_heap_string;
typedef   priority_queue<int, vi, greater<int>> min_heap_int;


// class Timer { private: chrono::time_point <chrono::steady_clock> Begin, End; public: Timer () : Begin(), End ()
// { Begin = chrono::steady_clock::now(); } ~Timer () { End = chrono::steady_clock::now();
// cout << "\nDuration: " << ((chrono::duration <double>)(End - Begin)).count() << "s\n"; } } t;

lli row , col , x, q;
vector<pair<lli , lli>> deleted;

lli getCount(lli n) {
    lli c = min(col , n-1);
    return c*(c+1)/2;
}

//If the number is in the range that has been deleted then decrease the count of this number
lli getDeletedCount(lli val) {
    
    lli cnt = 0;
    for(auto &k : deleted) {
        if(k.first > val) continue;
        else if(val >= k.second) cnt += k.second - k.first + 1;
        else if(val >= k.first and val < k.second)  cnt += val - k.first + 1;
    }
    return cnt;
}

lli query(lli k) {
    lli low = 2 , high = row+col , sumOfTwoNumbers = row + col + 2 , middle = (low+high) >> 1 ;
    
    bool even = false;
    if((row+col) % 2) even = false;
    else even = true;
    
    while(low <= high) {
        lli mid = (low+high) >> 1;
        lli currentCount;
        
        if(mid <= middle) 
            currentCount = getCount(mid);
        else 
        {
            if(!even)
                currentCount = 2 * getCount(middle) - getCount(sumOfTwoNumbers - mid - 1);
            else 
                currentCount = 2 * getCount(middle-1) - getCount(sumOfTwoNumbers - mid - 1) + min(middle-1 , col);
        }
        
        currentCount -= getDeletedCount(mid);
        
        if(currentCount == k ) return mid;
        else if(k < currentCount) high = mid-1;
        else low = mid+1;
    }
    
    return low;
}
void solve(){  
    
    
    cin >> row >> col >> x >> q;
    
    while(q--) {
        int type;
        lli a , b , c;
        cin >> type;
        
        if(type == 1 || type == 2) {      //type 1 | 2 queries
            cin >> a >> b >> c;
            deleted.pb({a+b , a+c});
        }
        else {                  //type 3 queries
            cin >> a;
            
            lli qa ;
            qa = query(a);
            
            // Answer can not be greater than N+M
            if(qa > (row + col)) {
                cout << "-1\n";
            }
            else 
                cout<< qa + x << "\n";  
        }
    }
    
} 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
	
	return 0;
}