// khodaya khodet komak kon
# include <bits/stdc++.h>
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 1e2 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;//998244353;
const int base = 257;
 
int qq, n, a[xn], mn, ans;
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> qq;
	while (qq --){
		cin >> n, mn = inf, ans = 0;
		for (int i = 1; i <= n; ++ i)
			cin >> a[i], mn = min(mn, a[i]);
		for (int i = 1; i <= n; ++ i)
			ans += a[i] != mn;
		cout << ans << endl;
	}
 
	return 0;
}

// khodaya khodet komak kon
// Nightcall - London Grammer
# include <bits/stdc++.h>
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 1e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;//998244353;
const int base = 257;
 
int qq, n, a[xn], ans, mn;
bool flag;
 
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
	cin >> qq;
	while (qq --){
		cin >> n, ans = 0;
		for (int i = 1; i <= n; ++ i)
			cin >> a[i], ans += (a[i] <= 0);
		sort(a + 1, a + n + 1), mn = inf;
		for (int i = 1; i <= n; ++ i)
			if (a[i] > 0)
				mn = min(mn, a[i]);
		flag = (mn < inf);
		for (int i = 2; i <= n; ++ i)
			if (a[i] <= 0)
				flag &= (a[i] - a[i - 1] >= mn);
		if (flag)
			cout << ans + 1 << endl;
		else
			cout << ans << endl;
	}
 
	return 0;
}

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
 
const int N = 2e5 + 10;
ll dp[2][N]; int A[2][N], n; vector<int> adj[N];
 
void DFS(int v, int p = -1) {
    dp[0][v] = dp[1][v] = 0;
    for (int u : adj[v]) {
        if (u == p) continue;
        DFS(u, v);
        dp[0][v] += max(abs(A[0][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[0][v] - A[0][u]));
        dp[1][v] += max(abs(A[1][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[1][v] - A[0][u]));
    }
}
 
void Solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &A[0][i], &A[1][i]);
    fill(adj + 1, adj + n + 1, vector<int>());
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    DFS(1);
    printf("%lld\n", max(dp[0][1], dp[1][1]));
}
 
int main() {
    int t; scanf("%d", &t);
    while (t--) Solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
#define X first
#define Y second
#define endl '\n'
 
const int N = 1e6 + 10;
const int MOD = 998244353;
 
int n, dp[N], S;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + i; j <= n; j += i) {
            dp[j]++;
        }
    }
    dp[0] = S = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = (dp[i] + S) % MOD;
        S = (S + dp[i]) % MOD;
    }
    cout << dp[n] << endl;
    return 0;
}

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=300010, LOG=20;
 
int n, m, k, u, v, x, y, t, a, b, ans;
int par1[MAXN], par2[MAXN];
int stt[MAXN], fnt[MAXN], timer;
vector<int> G1[MAXN], G2[MAXN];
set<pii> st;
 
int Add(int v){
	auto it=st.lower_bound({stt[v], v});
	if (it!=st.end() && fnt[it->second]<=fnt[v]) return -2;
	if (it==st.begin()) return -1;
	--it;
	int res=it->second;
	if (fnt[v]>fnt[res]) return -1;
	st.erase(it);
	return res;
}
void dfs1(int node){
	stt[node]=timer++;
	for (int v:G2[node]) dfs1(v);
	fnt[node]=timer;
}
void dfs2(int node){
	int res=Add(node);
	if (res!=-2) st.insert({stt[node], node});
	ans=max(ans, (int)st.size());
	for (int v:G1[node]) dfs2(v);
	if (res!=-2){
		st.erase({stt[node], node});
		if (res!=-1) st.insert({stt[res], res});
	}
}
 
void Solve(){
	cin>>n;
	for (int i=1; i<=n; i++) G1[i].clear(), G2[i].clear();
	for (int i=2; i<=n; i++) cin>>par1[i], G1[par1[i]].pb(i);
	for (int i=2; i<=n; i++) cin>>par2[i], G2[par2[i]].pb(i);
	timer=1;
	ans=0;
	dfs1(1);
	dfs2(1);
	cout<<ans<<"\n";
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int T;
	cin>>T;
	while (T--) Solve();
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
#define X first
#define Y second
#define endl '\n'
 
const int N = 3e5 + 10;
 
int t, n, L[N], R[N], timer, now, ans;
vector<int> Srsh[N], Msht[N];
set<pii> st;
 
void MshtDFS(int u) {
    L[u] = timer++;
    for (int v : Msht[u]) {
        MshtDFS(v);
    }
    R[u] = timer;
}
 
int ispar(int u, int v) {
    return L[u] <= L[v] && R[v] <= R[u];
}
 
void SrshDFS(int u) {
    int last = now;
    // add u
    auto it = st.lower_bound({L[u], 0});
    if (it != st.end())
        now += 1 - ispar(u, it->Y);
    if (it != st.begin()) {
        auto nxt = it--;
        now += 1 - ispar(it->Y, u);
        if (nxt != st.end())
            now -= 1 - ispar(it->Y, nxt->Y);
    }
    st.insert({L[u], u});
    ans = max(ans, now);
    // DFS
    for (int v : Srsh[u]) {
        SrshDFS(v);
    }
    // remove u
    st.erase({L[u], u});
    now = last;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> t;
    while (t --> 0) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            Srsh[i].clear();
            Msht[i].clear();
        }
        for (int u = 2; u <= n; u++) {
            int par; cin >> par;
            Srsh[par].push_back(u);
        }
        for (int u = 2; u <= n; u++) {
            int par; cin >> par;
            Msht[par].push_back(u);
        }
        timer = 0;
        MshtDFS(1);
        ans = now = 0;
        SrshDFS(1);
        cout << ans + 1 << endl;
    }
    return 0;
}

#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
    
class FenwickTree:
    def __init__(self, x):
        """transform list into BIT"""
        self.bit = x
        for i in range(len(x)):
            j = i | (i + 1)
            if j < len(x):
                x[j] += x[i]
    def update(self, idx, x):
        """updates bit[idx] += x"""
        while idx < len(self.bit):
            self.bit[idx] += x
            idx |= idx + 1
 
    def query(self, end):
        """calc sum(bit[:end])"""
        end += 1
        x = 0
        while end:
            x += self.bit[end - 1]
            end &= end - 1
        return x
 
    def findkth(self, k):
        """Find largest idx such that sum(bit[:idx]) <= k"""
        idx = -1
        for d in reversed(range(len(self.bit).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(self.bit) and k >= self.bit[right_idx]:
                idx = right_idx
                k -= self.bit[idx]
        return idx + 1
 
g1 = []
g2 = []
st = []
ft = []
 
def dfs1(graph, start=0):
    n = len(graph)
    tim = 1
    visited = [False] * n    
    stack = [start]
    while stack:
        start = stack[-1]
        if not visited[start]:
            st[start] = tim
            tim = tim + 1
            visited[start] = True
            for child in graph[start]:
                if not visited[child]:
                    stack.append(child)
        else:
            stack.pop()
            ft[start] = tim
 
 
 
def Do(v):
    global ans , cnt , mem
    fen.update(st[v] , 1);
    if(fen.query(ft[v] - 1) - fen.query(st[v])):
        mem += [[v , 0 , 0]]
        return;
    u = fen2.query(st[v]);
    ok[v] = 1
    cnt += 1
    fen2.update(st[v] , v - u)
    fen2.update(ft[v] , u - v)
    mem += [[v , u , ok[u]]]
    cnt -= ok[u]
    ok[u] = 0
    return;
 
 
 
def undo():
    global cnt , ans , mem
    [v , u , a] = mem[-1]
    if(a != 0):
        ok[u] = 1
        cnt += 1
    cnt -= 1
    ok[v] = 0
    fen.update(st[v] , -1)
    fen2.update(st[v] , u - v)
    fen2.update(ft[v] , v - u)
    mem.pop()
    return;
 
 
def dfs(graph, start=0):
    global ans , cnt
    n = len(graph)
    visited = [False] * n   
    stack = [start]
    while stack:
        start = stack[-1]
        if not visited[start]:
            Do(start)
            ans = max(ans , cnt)
            visited[start] = True
            for child in graph[start]:
                if not visited[child]:
                    stack.append(child)
        else:
            stack.pop()
            undo()
 
 
 
def solve():
    global n, g1 , g2 , V , st , ft , fen , fen2 , mem , ok , cnt , ans 
    n = int(input())
    if(n == 1):
        print(1)
        exit(0)
    
    g1 = [] ; g2 = []
    
    for i in range(n):
        g1.append([])
        g2.append([])
    
    # 0 base 
    
    V = list(map(int , input().split()))
    
    for i in range ( 1 , n ):
        v = V[i - 1]-1
        g1[v].append(i)
    
    V = list(map(int , input().split()))    
    
    for i in range ( 1 , n ):
        v = V[i-1]-1
        g2[v].append(i)
    st = [0] * (n + 100)
    ft = [0] * (n + 100)
    fen = FenwickTree([0] * (n + 3))
    fen2 = FenwickTree([0] * (n + 3))
    mem = []
    ok = [0]*(n + 100)
    cnt = 0
    ans = 0
    dfs1(g2)
    dfs(g1)
    print(ans)
 
q = int(input())
for i in range (q):
    solve()

#include<bits/stdc++.h>
#define lc (id * 2)
#define rc (id * 2 + 1)
#define md ((s + e) / 2)
#define dm ((s + e) / 2 + 1)
#define ln (e - s + 1)
using namespace std;
 
typedef long long ll;
const ll MXN = 3e5 + 10;
const ll MXS = MXN * 4;
ll n, timer, ans, Ans;
ll lazy[MXS], seg[MXS];
ll Stm[MXN], Ftm[MXN];
vector<ll> adj[MXN][2];
void Build(ll id = 1, ll s = 1, ll e = n){
    lazy[id] = -1, seg[id] = 0;
    if(ln > 1) Build(lc, s, md), Build(rc, dm, e);
}
void Shift(ll id, ll s, ll e){
    if(lazy[id] == -1) return;
    seg[id] = lazy[id];
    if(ln > 1) lazy[lc] = lazy[rc] = lazy[id];
    lazy[id] = -1;
}
void Upd(ll l, ll r, ll x, ll id = 1, ll s = 1, ll e = n){
    Shift(id, s, e);
    if(e < l || s > r) return;
    if(l <= s && e <= r){
        lazy[id] = x; Shift(id, s, e);
        return;
    }
    Upd(l, r, x, lc, s, md), Upd(l, r, x, rc, dm, e);
    seg[id] = max(seg[lc], seg[rc]);
}
ll Get(ll l, ll r, ll id = 1, ll s = 1, ll e = n){
    Shift(id, s, e);
    if(e < l || s > r) return 0;
    if(l <= s && e <= r) return seg[id];
    return max(Get(l, r, lc, s, md), Get(l, r, rc, dm, e));
}
void prep(ll u, ll par, ll f){
    Stm[u] = ++ timer;
    for(auto v : adj[u][f]){
        if(v != par) prep(v, u, f);
    }
    Ftm[u] = timer;
}
bool Is_Jad(ll j, ll u){
    return (Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j]);
}
void DFS(ll u, ll par, ll f){
    ll j = Get(Stm[u], Ftm[u]);
    if(!j) Upd(Stm[u], Ftm[u], u), ans ++;
    else{
        if(Is_Jad(j, u)){
            Upd(Stm[j], Ftm[j], 0);
            Upd(Stm[u], Ftm[u], u);
        }
    }
    Ans = max(Ans, ans);
    for(auto v : adj[u][f]){
        if(v != par) DFS(v, u, f);
    }
    if(!j) Upd(Stm[u], Ftm[u], 0), ans --;
    else{
        if(Is_Jad(j, u)){
            Upd(Stm[u], Ftm[u], 0);
            Upd(Stm[j], Ftm[j], j);
        }
    }
}
void solve(){
    cin >> n, timer = ans = Ans = 0;
    for(int i = 1; i <= n; i ++) adj[i][0].clear(), adj[i][1].clear();
    for(int t = 0; t < 2; t ++) for(int u = 2, v; u <= n; u ++){
        cin >> v, adj[v][t].push_back(u), adj[u][t].push_back(v);
    }
    Build(), prep(1, 0, 1);
    DFS(1, 0, 0);
    cout << Ans << '\n';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    ll q; cin >> q;
    while(q --) solve();
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int N=605;
 
int n, m, k, u, v, x, y, t, a, b;
bool mark[N];
int G[N][N], D[N];

inline void upd(int &x, int y){ if (x>y) x=y;}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	memset(G, 63, sizeof(G));
	cin>>n>>m;
	while (m--){
		cin>>u>>v>>x;
		G[u][v]=min(G[u][v], x);
	}
	for (int i=0; i<n; i++){
		memset(D, 63, sizeof(D));
		memset(mark, 0, sizeof(mark));
		for (int v=0; v<n; v++) upd(D[v], G[i][v]);
		while (1){
			int v=-1;
			for (int x=0; x<n; x++) if (!mark[x]){
				if (v==-1 || D[v]>D[x]) v=x;
			}
			if (v==-1) break ;
			mark[v]=1;
			upd(D[(v+1)%n], D[v]+1);
			for (int u=0; u<n; u++)
				upd(D[(u+D[v])%n], D[v]+G[v][u]);
			
		}
		for (int j=0; j<n; j++){
			if (i==j) cout<<"0 ";
			else cout<<D[j]<<" ";
		}
		cout<<"\n";
	}
	
	return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 600 + 5;
 
int n;
int dp[maxn];
bool mark[maxn];
vector<pair<int,int>> g[maxn];
int go[maxn];
 
int dis(int s, int t) {
	if (s <= t)
		return t - s;
	return n - (s - t);
}
 
void dijkstra(int src) {
	memset(dp, 63, sizeof dp);
	memset(mark, 0, sizeof mark);
	dp[src] = 0;
	set<int> S;
	for (int i = 0; i < n; i++)
		S.insert(i);
	for (int i = 0; i < n - 1; i++) {
		int v = -1;
		for (int j = 0; j < n; j++) {
			if (mark[j])
				continue;
			if (v == -1 or dp[v] > dp[j])
				v = j;
		}
		S.erase(v);
		mark[v] = 1;
		if (v != src) {
			auto it = S.lower_bound(v);
			if (it == S.end())
				it = S.lower_bound(0);
			int nex = *it;
			dp[nex] = min(dp[nex], dp[v] + dis(v, nex));
		}
		for (int i = 2 * n - 1; i >= 0; i--) {
			int v = i % n;
			if (!mark[v])
				go[v] = v;
			else
				go[v] = go[(v + 1) % n];
		}
		for (auto [u, w] : g[v]) {
			int nex = go[(u + dp[v]) % n];
			dp[nex] = min(dp[nex], dp[v] + w + dis((u + dp[v]) % n, nex));
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	int m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) { 
		int v, u, w;
		cin >> v >> u >> w;
		g[v].push_back({u, w});
	}
	for (int i = 0; i < n; i++) {
		dijkstra(i);
		for (int j = 0; j < n; j++)
			cout << dp[j] << " \n"[j == n-1];
	}
}

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=998244353, inv6=166374059;
const int MAXN=1000010, LOG=20;
 
ll n, m, k, u, v, x, y, t, a, b, ans;
ll dp[MAXN], ps[MAXN];
ll pd[MAXN], sp[MAXN];
 
ll C3(ll x){
	return x*(x-1)%mod*(x-2)%mod*inv6%mod;
}
ll C2(ll x){
	return x*(x-1)/2%mod;
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	dp[0]=ps[0]=1;
	pd[0]=sp[0]=1;
	for (int i=1; i<=n; i++){
		ps[i]=(1 + ps[i-1] + ps[i-1]*(ps[i-1]+1)/2)%mod;
		dp[i]=ps[i]-ps[i-1];
		pd[i]=dp[i]-dp[i-1];
		sp[i]=(sp[i-1]+pd[i])%mod;
	}
	for (int i=0; i<n; i++) ans=(ans + pd[i]*sp[n-1-i])%mod;
	
	ans=(ans + 2*C3(ps[n-1]+2))%mod;
	if (n>=2) ans=(ans - 2*C3(ps[n-2]+2))%mod;
	
	ans=(ans + 2*C2(ps[n-1]+1))%mod;
	if (n>=2) ans=(ans - 2*C2(ps[n-2]+1))%mod;
	
	if (ans<0) ans+=mod;
	cout<<ans<<"\n";
	
	return 0;
}

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=998244353;
const int MAXN=3000010, LOG=18;
 
int n, m, k, u, v, x, y, t, a, b;
int rev[MAXN];
ll F[MAXN], I[MAXN];
ll A[MAXN], B[MAXN], ans;
 
ll powmod(ll a, ll b){
	ll res=1;
	for (; b; b>>=1, a=a*a%mod) if (b&1) res=res*a%mod;
	return res;
}
ll nCr(ll n, ll r){
	if (r<0 || r>n) return 0;
	return F[n]*I[r]%mod*I[n-r]%mod;
}
 
void NTT(ll *A, bool inv){
	int n=(1<<LOG);
	for (int i=0; i<(1<<LOG); i++) if (rev[i]<i) swap(A[i], A[rev[i]]);
	for (int ln=1; ln<n; ln<<=1){
		ll w=powmod(3, mod/2/ln);
		if (inv) w=powmod(w, mod-2);
		for (int i=0; i<n; i+=2*ln){
			ll wn=1;
			for (int j=i; j<i+ln; j++){
				ll x=A[j], y=A[j+ln]*wn;
				A[j]=(x+y)%mod;
				A[j+ln]=(x-y)%mod;
				wn=wn*w%mod;
			}
		}
	}
	if (inv){
		ll invn=powmod(1<<LOG, mod-2);
		for (int i=0; i<n; i++) A[i]=A[i]*invn%mod;
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	F[0]=1;
	for (int i=1; i<MAXN; i++) F[i]=F[i-1]*i%mod;
	I[MAXN-1]=powmod(F[MAXN-1], mod-2);
	for (int i=MAXN-1; i; i--) I[i-1]=I[i]*i%mod;
	for (int i=1; i<(1<<LOG); i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(LOG-1));
	
	cin>>n>>k;
	for (int i=0; i<=k; i++){
		A[i]=powmod(i, k)*I[i]%mod;
		B[i]=I[i];
		if (i&1) B[i]*=-1;
	}
	NTT(A, 0);
	NTT(B, 0);
	for (int i=0; i<MAXN; i++) A[i]=A[i]*B[i]%mod;
	NTT(A, 1);
	ll mul=1;
	for (int i=0; i<=min(n, k); i++){
		ll val=mul*powmod(n+1, n-i)%mod;
		ans=(ans + val*A[i])%mod;
		mul=mul*(n-i)%mod;
	}
	if (ans<0) ans+=mod;
	cout<<ans<<"\n";
	
	return 0;
}