問題文

以下の条件を満たす整数の組 x,y がいくつあるかを求めて下さい。

• 0 \leq x, y \leq N
• Ax+By は C の倍数

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

3 点の部分点のデータでは以下の条件を満たします。

• T = 1
• 1 \leq N \leq 1000
• 1 \leq A,B,C \leq 10^9

満点のデータでは以下の条件を満たし、上記とは別に 1 点が与えられます。（満点解法はとても難しいので、一旦飛ばすことをおすすめします。）

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^9
• 1 \leq A,B,C \leq 10^9

入力例 1

1
2 3 4 5

出力例 1

2

入力例 2

1
1000 314159265 271828182 2023

出力例 2

496

問題文

N 頂点の根付き木があります。根は頂点 1 です。頂点 i (2 \leq i \leq N) の親は頂点 P_i です。

各 i (1 \leq i \leq N) について、頂点 i を根とする部分木の頂点数を求めて下さい。すなわち、頂点 j から頂点 1 へ到達するために必ず頂点 i を経由する必要のあるような j の個数を求めて下さい。

制約

入力は以下の条件を満たす。

• 2 \leq N \leq 5 \times 10^5
• 入力されるグラフは木をなす。

入力例 1

4
1
2
2

出力例 1

4
3
1
1

入力例 2

10
1
2
3
2
1
5
6
3
4

出力例 2

10
7
4
2
2
2
1
1
1
1