문제

$N$개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 주어진다. 각 정점은 $1$부터 $N$까지 순서대로 번호가 매겨져 있고, 루트는 $1$번 정점이다.

여러분은 트리의 루트에서 시작해 DFS(Depth-First Search)를 수행했다. 단, 한 정점에서 방문할 수 있는 인접한 자식 정점이 여러 개라면 정점 번호가 작은 정점 순서대로 먼저 방문한다. 그 과정에서 어떤 정점에 처음 진입했을 때 1을, 그 정점에서 빠져나올 때 0을 공책에 기록하고 순서대로 이어붙였다. 이렇게 만들어진 길이가 $2N$인 문자열을 $S$라고 하자.

여러분은 0개 이상 1개 이하의 정점에 대해서 특별히 그 정점의 자식 정점 방문 순서를 임의로 재배열하여 방문할 수 있다. 그 상태에서 이전처럼 DFS를 수행하여 만들어진 문자열을 $S'$이라 하자. 이때 가능한 모든 $S'$ 중, 사전순으로 가장 앞서는 문자열을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 ≤ T ≤ 100\,000)$

이후, 각 테스트 케이스의 첫째 줄에 $N$이 주어진다. $(1\le N\le 100\,000)$

둘째 줄에는 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어지는데 각각 $i$번 정점의 부모는 $P_i$라는 의미다. 단, $1$번 정점의 부모는 존재하지 않으므로 $P_1$은 -1로 주어진다.

모든 테스트케이스에서 $N$의 합은 $100\,000$을 초과하지 않는다.

출력

각 테스트 케이스에 대해서, 가능한 모든 $S'$ 중 사전순으로 가장 앞서는 문자열을 출력한다.

예제 입력 1

2
5
-1 1 1 2 2
1
-1

예제 출력 1

1101101000
10

첫 번째 테스트 케이스에서, 1번 정점에서 2번 정점보다 3번 정점을 먼저 방문하도록 방문 순서를 재배열하는 방법이 최선이다.

노트

트리는 무방향 사이클이 없는 연결 그래프를 의미한다.