404993: GYM101727 E Backup

To ensure user data is safe and won't be loss in an accident Arkady always invents and tests new ways to organize backup. This time he enumerated all computers he possess from 1 to n and for each computer with index from 1 to n - 1 identified backup computer p_i. He followed the rule that the index of backup computer should always be greater than the index of a computer itself, i.e. p_i > i. Because of this rule there is no backup for computer n.

During the current experiment Arkady has chosen some configuration of values p_i and now plans to turn computers off in some order, one computer every second. The experiment is over when computer with index n is turned off. Initially, each computer has a block of data of size 1. When computer x is turned off, its block of data of size 1 is copied to computer p_x. In case there were some other block at computer x (that were received as a backup from other computers) and they are not copied and are considered lost. Moreover, if computer p_x is already off, the block of data from computer x is not copied anywhere and is also considered lost.

Akrady wants his experiment to last as long as possible. However, he has to follow one more rule: if during some second the number of blocks of data that has gathered at some machine is equal to k, this machine must be turned off during next second to ensure hardware safety. Note, that the last second (when computer n is turned off) is not counted.

The first line of the input contains a single integer t (1 ≤ t ≤ 20) — the number of tests.

Then follow t individual tests descriptions. Each description starts with two integers n and k (1 ≤ n ≤ 100 000, 2 ≤ k ≤ 10) — the number of computers that take part in this experiment and the maximum possible load of one computer. Next line contains n - 1 integers p₁, p₂, ..., p_n - 1 (i + 1 ≤ p_i ≤ n).

For each of t tests print one integer equal to the maximum possible number of seconds before Arkady will have to turn off machine number n.

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

10 3
8 8 8 9 9 9 10 10 10

2
3
0
7