Queuing at the Doctors

Because of various strange viruses spreading around, every member of the International Confederation of Revolver Enthusiasts (ICORE) must undergo a quarterly physical checkup at General Hospital. All checkups are arranged by the boss and scheduled on the same day. Each member receives instructions that give:

• their number from the set {1, ..., n};
• the time of day when they must show up at General Hospital;
• the list of doctors' offices they must visit, in the given order.

The doctors' offices are numbered {1, ..., m}.

Everyone was told the schedule was prepared professionally so that no one would have to line up and wait. Reality was different: queues formed quickly. The members are all disciplined and follow these rules:

• if a member is supposed to arrive at time t, then at time t they appear at the first office on their list;
• if several people appear at an office at the same time t, they line up in increasing order of their numbers and join the end of the queue already formed by people who arrived earlier;
• if at time t there is a queue at office x made of people who arrived at or before time t, then the first person in the queue enters office x. After one time unit that person leaves the office and, at time t+1, appears at the next office on their list; at that same moment the next person in the queue enters office x;
• if the visit to office x at time t was the visitor's last, then at time t+1 that visitor leaves the hospital.

Determine the time at which the last visitor leaves the hospital.

The first line contains a natural number c, the number of test cases. Each test case follows in the format below.

The first line of a case contains two natural numbers n and m (1 ≤ n, m ≤ 1000): the number of visitors and the number of doctors' offices. Each of the next n lines describes one visitor. Line i (1 ≤ i ≤ n) has the form

t k g_1 g_2 ... g_k

meaning that visitor i arrives at time t and must visit k offices in the order g_1, g_2, ..., g_k, where 1 ≤ g_j ≤ m. It is guaranteed that 0 ≤ t ≤ 1000000 and that no more than 1000000 visits are scheduled for the whole day.

For each of the c test cases, print a single line with the time at which the last visitor leaves the hospital.