Deep within the vaults of the Infinity Casino, past the roulette tables and slot machines, there lies a secret table — one reserved for masterminds of logic. It's called Tree Royale, and tonight, Parsa is invited to play.

On the velvet table lie ~n~ rooted trees, each glowing with magical energy. The game is simple... yet dangerously clever:

"You may merge the trees one by one," says the Dealer. "Each time, take the root of one tree and connect it to any node of another — but only if the new graph remains a valid rooted tree."

Parsa nods. He knows the rules:

• At every step, only one root can connect to another tree.
• The merging continues until there is only one tree left — The Final Tree.

The Dealer leans forward with a grin: "If you play optimally... what will be the diameter of your final masterpiece?"

Can you help Parsa determine the maximum possible diameter of the final rooted tree that results from merging the initial ~n~ trees, using the rules above?

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 10^5~). The description of the test cases follows.

The first line of each test case contains an integer ~n~ (~1 \le n \le 10^6~) — the number of rooted trees.

Then, for each of the ~n~ trees, the following data is provided:

• A line containing a single integer ~m~ (~1 \le m \le 10^6~), the number of vertices in the current tree.
• The next line contains ~m - 1~ integers ~p_2, p_3, ..., p_m~, where each ~p_i~ (~1 \le p_i < i~) denotes the parent of vertex ~i~. Vertex ~1~ is the root of the tree. (Note that if ~m = 1~, this line will be empty.)

It is guaranteed that the total number of vertices across all trees in all test cases does not exceed ~10^6~.

Output

For each test case print one number, the maximum possible diameter of the final rooted tree.

Clarifications

The diameter of a tree is defined as the longest path between any two nodes in the tree.

Examples

Input 1

2
2
4
1 2 3
6
1 2 1 3 4
3
4
1 2 2
3
1 1
3
1 2

Output 1

9
8