There are two doctors and two patients, and each doctor needs to perform one surgery on each patient. To prevent direct contact between the doctor's hands and the patient, the doctor must wear gloves during surgery. However, after use, the inner surface of the glove becomes contaminated with the doctor's sweat, and the outer surface becomes contaminated with the patient's blood. Neither the doctors nor the patients are willing to come into contact with anyone else's sweat or blood. Now, there are only two pairs of gloves; how can these four surgeries be completed?

Using traditional methods, it is impossible to complete four surgeries with only two pairs of gloves. Therefore, we thought of a magical method—nesting the two pairs of gloves together! However, nesting gloves can lead to damage at the contact surfaces. Based on years of clinical experience, the contact surfaces will not be damaged only if both contact surfaces are brand new (free of any sweat or blood and never damaged before); otherwise, both contact surfaces will be damaged. If a surface of a glove is damaged, neither the doctor nor the patient will be willing to touch that surface. After trying various methods, we arrived at the following solution:

• Step 1: Doctor $0$ performs surgery on patient $0$, using glove $b$ nested over glove $a$ (glove $b$ is on the outside);
• Step 2: Doctor $0$ performs surgery on patient $1$, using glove $a$;
• Step 3: Doctor $1$ performs surgery on patient $0$, using glove $b$;
• Step 4: Doctor $1$ performs surgery on patient $1$, using glove $a$ nested over glove $b$ (glove $a$ is on the outside).

Obviously, wearing too many gloves affects the quality of the surgery, so we stipulate that at most two pairs of gloves can be nested together in one surgery. Now, we have $n$ doctors and $m$ patients, where certain doctors need to perform surgeries on certain patients. Please help calculate the minimum number of glove pairs required to complete all surgeries.

It is worth noting that: a pair of gloves is treated as a single unit and cannot be split into "two individual gloves" for separate use. Additionally, if necessary, gloves can be used "inside out."

Input

The first line of the input contains a positive integer $T$, representing the number of test cases in the file.

For each test case: The first line contains three positive integers $n$, $m$, and $s$. These represent $n$ doctors (numbered $0$ to $n-1$), $m$ patients (numbered $0$ to $m-1$), and $s$ surgeries (numbered $0$ to $s-1$). The following $s$ lines describe each surgery in order of their ID. Each line contains two non-negative integers $x$ and $y$, indicating that doctor $x$ and patient $y$ need to perform a surgery. It is guaranteed that no two identical surgeries will occur.

Output

The output should contain the answers for $T$ test cases.

For each set of answers: The first line contains a positive integer $p$, representing the number of glove pairs you need to use (numbered sequentially starting from the letter $\texttt{a}$). Then, $s$ lines follow, where you must describe each surgery arrangement in chronological order, with each surgery on a separate line. For a surgery, you must first output its ID, then the number of glove pairs $k$ used (must be $1$ or $2$), and then output the IDs (letters) of the $k$ glove pairs in order from inside to outside (from doctor to patient), separated by spaces. Specifically, if a pair of gloves is used in an "inside out" state during that surgery, represent it with the corresponding uppercase letter; otherwise, use the lowercase letter, as shown in the examples.

Examples

Input 1

2  
2 2 4  
0 1  
0 0  
1 0  
1 1  
3 2 3  
0 1  
1 0  
2 0

Output 1

2  
0 2 a b  
1 1 a  
2 1 b  
3 2 A B  
3  
0 2 a b  
1 2 A B  
2 1 c

Constraints