Scrambled Digits
시간 제한2초메모리 제한512 MB
Petya가 그린 선분 목록이 주어질 때, 크기가 바뀌고 회전된 다섯 숫자가 각각 몇 번 그려졌는지 셉니다.
문제
어린 Petya는 숫자 쓰는 법을 막 배우기 시작했고, 지금은 아래 5개의 숫자를 쓰는 연습을 하고 있습니다.
Petya는 각 숫자를 위 그림과 정확히 같은 크기로 그리지만, 다음 변경을 0번 이상 적용할 수 있습니다.
- 숫자의 너비를 줄이거나 늘린다. 너비는 단위의 정수배로 유지한다.
- 숫자의 높이를 줄이거나 늘린다. 높이는 단위의 정수배로 유지한다.
- 숫자를 시계 방향으로 90도, 180도, 또는 270도 회전한다.
숫자의 너비나 높이를 바꿔도 선분의 두께는 변하지 않으며, 숫자 전체에 똑같이 영향을 줍니다. 예를 들어 회전하기 전의 숫자 3을 세로로 늘이거나 줄여도, 가운데 수평 선분은 항상 다른 수평 선분의 정확히 가운데에 위치합니다.
Petya는 무한한 2차원 평면에 많은 숫자를 쓰며, 다음 규칙을 지킵니다.
- 숫자끼리는 닿거나 겹치지 않는다. 한 숫자의 선분은 다른 숫자의 선분에 닿지 않는다.
- 모든 세로 선분은 정수 X값을 가진 세로선 위에 놓인다.
- 모든 가로 선분은 정수 Y값을 가진 가로선 위에 놓인다.
- 모든 끝점은 정수 좌표에 있다. 끝점은 세로 또는 가로 선분의 끝에 있는 점을 뜻한다.
Petya는 선분을 그려 숫자를 씁니다. 각 선분은 정수 좌표의 두 점을 잇고, 모든 선분은 양의 정수 길이를 가진 세로 또는 가로 선분입니다. 선분끼리 닿거나 심지어 겹칠 수도 있지만, 그럴 때는 같은 숫자의 같은 인스턴스에 속합니다(두 번째 예제 테스트 케이스 참고).
다음 그림은 입력에 절대 나타나지 않는 잘못된 숫자들입니다.
1은 잘못 회전되었고, 3의 가운데 수평 선분 길이가 틀렸으며, 2의 가운데 수평 선분이 더 이상 가운데에 있지 않고, 4는 회전이 아니라 거울상입니다.
Petya가 그린 선분 목록이 주어집니다. 입력은 위에서 설명한 올바른 숫자만 만들어진다고 보장됩니다. 각 숫자가 몇 번 그려졌는지 세어 주세요.
입력
첫 줄에 테스트 케이스의 개수 T가 주어집니다(1 ≤ T ≤ 100). 각 테스트 케이스는 선분의 개수 N이 적힌 줄로 시작합니다(1 ≤ N ≤ 100,000). 이어서 N개의 줄이 주어지며, 각 줄에는 정수 네 개 , , , 가 있습니다. 이는 점 과 점 를 잇는 선분을 나타냅니다(1 ≤ X1, Y1, X2, Y2 ≤ 1,000,000,000).
출력
각 테스트 케이스마다 공백으로 구분된 정수 5개를 출력합니다. 각 정수는 해당 숫자가 그려진 횟수이며, 첫 번째 그림에 나온 왼쪽에서 오른쪽 순서를 따릅니다.
힌트
첫 번째 예제 테스트 케이스는 첫 번째 그림을 나타냅니다.
두 번째 예제 테스트 케이스는 다음 그림을 나타냅니다. 일부 선분은 겹치거나 닿아서 하나의 긴 선분을 이룹니다.
