Diamonds

The value of a diamond is set by its weight in carats and by its clarity. A small clear diamond is worth more than a large cloudy one. Clarity uses a scale from 0.0 to 10.0, where 0.0 is a perfectly clear diamond and 10.0 is the most flawed one.

You are given the weight $w_i$ and the clarity $c_i$ of $N$ diamonds in the order they appear in the input. Keeping that order, find the maximum length of a subsequence whose weight keeps growing while the clarity value keeps falling. If the chosen indices are $i_1 < i_2 < \cdots < i_k$, then every adjacent pair must satisfy $w_{i_j} < w_{i_{j+1}}$ and $c_{i_j} > c_{i_{j+1}}$. Neither condition allows equal values.

Consider this input data.

The longest subsequence that satisfies the condition has length 4 and consists of these four diamonds.

The weight keeps growing and the clarity value keeps falling.

The first line has the number of test cases $T$ ($1 \le T \le 100$). Each test case starts with a line holding the number of diamonds $N$ ($1 \le N \le 200$). The next $N$ lines each hold the weight $w_i$ and the clarity $c_i$ of one diamond, separated by a space ($0 \le w_i, c_i \le 100$).

For each test case, print on its own line the length of the longest subsequence whose weight increases and whose clarity value decreases.