[Solution] Sort the Fabrics Round F 2022 - Kick Start 2022 Solution

Problem

A fabric is represented by three properties:

• Color (C$C$), a string consisting of lowercase letters of the English alphabet, representing the color of the fabric.
• Durability (D$D$), an integer representing the durability of the fabric.
• Unique identifier (U$U$), an integer representing the ID of the fabric.

Ada and Charles work at the Kick Start fabric factory. Each day they receive N$N$ fabrics, and one of them has to sort it. They sort it using the following criteria:

• Ada sorts in lexicographically increasing order by color (C$C$).
• Charles sorts in ascending order by durability (D$D$).
• They break ties by sorting in ascending order by the unique identifier (U$U$).

Given N$N$ fabrics, count the number of fabrics which end up in the same position regardless of whether Ada or Charles sort them.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.
Each test case begins with one line consisting of an integer N$N$ denoting the number of fabrics. Then N$N$ lines follow, each line with a string Ci${\mathbf{C}}_{\mathbf{i}}$, an integer Di${\mathbf{D}}_{\mathbf{i}}$, and an integer Ui${\mathbf{U}}_{\mathbf{i}}$: the color, the durability and the unique identifier of the i$i$-th fabric respectively.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the number of fabrics which end up in the same position regardless of whether a worker sorts them by color or by durability.

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤$1\le$ length of string Ci${\mathbf{C}}_{\mathbf{i}}$ ≤10$\le 10$.
String Ci${\mathbf{C}}_{\mathbf{i}}$ consists of only lowercase letters of the English alphabet.
No two fabrics have same Ui${\mathbf{U}}_{\mathbf{i}}$.

Test Set 1

1≤N≤2$1\le \mathbf{N}\le 2$.
1≤Di≤2$1\le {\mathbf{D}}_{\mathbf{i}}\le 2$.
1≤Ui≤2$1\le {\mathbf{U}}_{\mathbf{i}}\le 2$.

Test Set 2

1≤N≤103$1\le \mathbf{N}\le {10}^3$.
1≤Di≤102$1\le {\mathbf{D}}_{\mathbf{i}}\le {10}^2$.
1≤Ui≤103$1\le {\mathbf{U}}_{\mathbf{i}}\le {10}^3$.

In Sample Case #1, when sorted by color, the order of fabrics represented by the unique identifier is 1$1$ and 2$2$. When sorted by durability, the order of fabrics is 2$2$ and 1$1$. Therefore, 0$0$ fabrics have the same position when sorted by color or durability.

In Sample Case #2, when sorted by color, the order of fabrics represented by the unique identifier is 1$1$ and 2$2$. When sorted by durability, the order of fabrics is also 1$1$ and 2$2$. Therefore, 2$2$ fabrics have the same position. Notice that both fabrics have the same durability, so when Charles sorts them he decides that fabric 1$1$ comes first because it has a smaller identifier.

In Sample Case #3, since there is only 1$1$ fabric, the position remains the same whether the fabrics are sorted by color or durability.