Description

To Mr. Solitarius, who is a famous solo play game creator, a new idea occurs like every day. His new game requires discs of various colors and sizes.

To start with, all the discs are randomly scattered around the center of a table. During the play, you can remove a pair of discs of the same color if neither of them has any discs on top of it. Note that a disc is not considered to be on top of another when they are externally tangent to each other.

Figure. Seven discs on the table

For example, in figure, you can only remove the two black discs first and then their removal makes it possible to remove the two white ones. In contrast, gray ones never become removable.

You are requested to write a computer program that, for given colors, sizes, and initial placings of discs, calculates the maximum number of discs that can be removed.

Input

The input consists of multiple datasets, each being in the following format and representing the state of a game just after all the discs are scattered.

n
x₁ y₁ r₁ c₁
x₂ y₂ r₂ c₂
…
x_n y_n r_n c_n

The first line consists of a positive integer n representing the number of discs. The following n lines, each containing 4 integers separated by a single space, represent the colors, sizes, and initial placings of the n discs in the following manner:

• (x_i, y_i), r_i, and c_i are the xy-coordinates of the center, the radius, and the color index number, respectively, of the i-th disc, and
• whenever the i-th disc is put on top of the j-th disc, i < j must be satisfied.

You may assume that every color index number is between 1 and 4, inclusive, and at most 6 discs in a dataset are of the same color. You may also assume that the x- and y-coordinates of the center of every disc are between 0 and 100, inclusive, and the radius between 1 and 100, inclusive.

The end of the input is indicated by a single zero.

Output

For each dataset, print a line containing an integer indicating the maximum number of discs that can be removed.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Running a taxi station is not all that simple. Apart from the obvious demand for a centralised coordination of the cabs in order to pick up the customers calling to get a cab as soon as possible, there is also a need to schedule all the taxi rides which have been booked in advance. Given a list of all booked taxi rides for the next day, you want to minimise the number of cabs needed to carry out all of the rides.

For the sake of simplicity, we model a city as a rectangular grid. An address in the city is denoted by two integers: the street and avenue number. The time needed to get from the address a, b to c, d by taxi is |a - c| + |b - d| minutes. A cab may carry out a booked ride if it is its first ride of the day, or if it can get to the source address of the new ride from its latest, at least one minute before the new rides scheduled departure. Note that some rides may end after midnight.

Input

3On the first line of the input is a single positive integer N, telling the number of test scenarios to follow. Each scenario begins with a line containing an integer M, 0 < M < 500, being the number of booked taxi rides. The following M lines contain the rides. Each ride is described by a departure time on the format hh:mm (ranging from 00:00 to 23:59), two integers a b that are the coordinates of the source address and two integers c d that are the coordinates of the destination address. All coordinates are at least 0 and strictly smaller than 200. The booked rides in each scenario are sorted in order of increasing departure time.

Output

For each scenario, output one line containing the minimum number of cabs required to carry out all the booked taxi rides.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N. No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.

Input

The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0.

Output

The output contains for each block except the last in the input file one line containing the number of critical places.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider the following exercise, found in a generic linear algebra textbook.

Let A be an n × n matrix. Prove that the following statements are equivalent:

(a) A is invertible.

(b) Ax = b has exactly one solution for every n × 1 matrix b.

(c) Ax = b is consistent for every n × 1 matrix b.

(d) Ax = 0 has only the trivial solution x = 0.

The typical way to solve such an exercise is to show a series of implications. For instance, one can proceed by showing that (a) implies (b), that (b) implies (c), that (c) implies (d), and finally that (d) implies (a). These four implications show that the four statements are equivalent.

Another way would be to show that (a) is equivalent to (b) (by proving that (a) implies (b) and that (b) implies (a)), that (b) is equivalent to (c), and that (c) is equivalent to (d). However, this way requires proving six implications, which is clearly a lot more work than just proving four implications!

I have been given some similar tasks, and have already started proving some implications. Now I wonder, how many more implications do I have to prove? Can you help me determine this?

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

• One line containing two integers n (1 ≤ n ≤ 20000) and m (0 ≤ m ≤ 50000): the number of statements and the number of implications that have already been proved.
• m lines with two integers s₁ and s₂ (1 ≤ s₁, s₂ ≤ n and s₁ ≠ s₂) each, indicating that it has been proved that statement s₁ implies statement s₂.

Output

Per testcase:

• One line with the minimum number of additional implications that need to be proved in order to prove that all statements are equivalent.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. K. I. has a very big movie collection. He has organized his collection in a big stack. Whenever he wants to watch one of the movies, he locates the movie in this stack and removes it carefully, ensuring that the stack doesn’t fall over. After he finishes watching the movie, he places it at the top of the stack.

Since the stack of movies is so big, he needs to keep track of the position of each movie. It is sufficient to know for each movie how many movies are placed above it, since, with this information, its position in the stack can be calculated. Each movie is identified by a number printed on the movie box.

Your task is to implement a program which will keep track of the position of each movie. In particular, each time Mr. K. I. removes a movie box from the stack, your program should print the number of movies that were placed above it before it was removed.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

one line with two integers n and m (1 ≤ n, m ≤ 100,000): the number of movies in the stack and the number of locate requests.

one line with m integers a₁, …, a_m (1 ≤ a_i ≤ n) representing the identification numbers of movies that Mr. K. I. wants to watch.

For simplicity, assume the initial stack contains the movies with identification numbers 1, 2, …, n in increasing order, where the movie box with label 1 is the top-most box.

Output

Per test case:

one line with m integers, where the i-th integer gives the number of movie boxes above the box with label a_i, immediately before this box is removed from the stack.

Note that after each locate request a_i, the movie box with label a_i is placed at the top of the stack.

Sample Input  Download

Sample Output  Download

Tags

Discuss