Chuỗi Điểm Ba Chiều

Description

Mỗi test gồm $N$ điểm khác nhau trong không gian ba chiều. Một điểm $(x_1,y_1,z_1)$ có thể đứng ngay trước $(x_2,y_2,z_2)$ khi cả ba tọa độ đều không giảm. Hãy tìm số điểm lớn nhất có thể chọn thành một chuỗi và số tập điểm đạt độ dài đó; hai phương án khác nhau nếu tập điểm được chọn khác nhau.

Input

• Dòng đầu chứa $T$.
• Mỗi test chứa $N$ và $N$ bộ ba tọa độ.

Output

• Mỗi test in $L$ $C$: độ dài lớn nhất và số phương án modulo $2^{30}$.

Constraints

• $1\le T\le 3$.
• $1\le N\le 10^5$ trong mỗi test.
• $0\le x,y,z\le 2^{30}$.
• Không có hai điểm trùng hoàn toàn trong cùng test.

Scoring

• Subtask $1$ ($50\%$ số điểm): dữ liệu nhỏ theo giới hạn được công bố trong hệ thống chấm.
• Subtask $2$ ($50\%$ số điểm): không có giới hạn bổ sung.

Example

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

3 2