题目描述

某日，小 A 和小 B 在一起开心地玩着游戏。

他们找了一棵以 $1$ 节点为根节点的树，很显然，作为一棵树，总有一个或好多个叶子节点。小 A 和小 B 玩的是回合制游戏。

每次小 A 或小 B 可以选择任意数量的叶子节点，将其从树中摘下（每次只能摘叶子节点，每次摘的数量不限制，但不能不摘，更不能摘的数量超过本来叶子节点的数量）。

很显然，把一些叶子摘下后，他们的父亲节点有可能会成为新的叶子节点，这时，这些新成为叶子节点的原父亲节点也变得可以被摘取了。

现在，小 A 先摘，小 B 再摘，往复循环。把 $1$ 号节点摘下的人获胜。我们知道，小 A 和小 B 总会按最优方式进行游戏，问谁会取得胜利。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，表示一共有 $T$ 组数据。

每组数据的第二行一个正整数 $n$，表示这棵树有 $n$ 个节点。

每组数据的第三行，$n-1$ 个整数，代表从 $2$ 号节点到 $n$ 号节点的父亲节点编号。

输出格式

共 $T$ 行，每行一个整数 $1$ 或 $0$。

$1$ 代表小 A 会取得胜利，$0$ 代表小 B 会取得胜利。

2
3
1 1
4
1 2 3

1
0

提示

本题数据随机，只要简单分析一下性质，就很好骗分，因此本题采用捆绑测试。

对于 $40\%$ 的数据：$1 \leq n \leq 100$。

对于 $100\%$ 的数据：$1 \leq n \leq 10^6$，$1 \leq T \leq 10$。

本题时空限制（尤其是空间）均非常宽松，不卡常，不毒瘤，请放心食用。