유명한 피타고라스의 정리와 유사한 형태의 피타고라스 기댓값 (Pythagorean Expectation)이 야구와 같은 스포츠 경기에 자주 사용된다. 피타고라스 기댓값은 빌 제임스(Bill James)에 의해 정의되었으며, 이 값은 특정 야구팀이 한 시즌 동안 얼마나 잘 했는지를 평가하는 지표 중 하나로 사용된다. 한 야구팀의 피타고라스 기댓값 (W)는 아래 식과 같이 정의된다.

(W = \dfrac{S^2}{S^2 + A^2}),

여기서 (S)는 해당 팀의 총 득점 수를, (A)는 해당 팀의 총 실점 수를 나타낸다.

이 기댓값을 실제 승률과 비교하여, 해당 팀이 한 시즌을 얼마나 잘 보냈는지 평가할 수 있다. 예를 들어, 한화 이글스는 2014 시즌에 619 득점과 889 실점을 했다. 즉, (S) = 619, (A) = 889이 되어, 한화 팀의 피타고라스 기댓값은 (W) = 619²/(619² + 889²) = 0.326이 된다. KBO 규정에 따르면, 한 시즌당 한 팀은 128번의 경기를 해야 하므로, 한화는 0.326 ×128 = 41.728 경기에서는 승리했어야 한다. 실제 한화는 49경기에서 승리했기 때문에, 2014 시즌을 그리 나쁘지 않게 보냈음을 알 수 있다. 반면에 롯데 자이언츠는 (S) = 715이고, (A) = 719이 되어, (W) = 0.497이 된다. 따라서 0.497 ×128 = 63.616경기 이상을 이길 것으로 기대되었지만, 실제론 58경기만 승리했다. 결국, 롯데에게 2014년은 기대에 많이 못 미친 시즌이었음을 알 수 있다.

(n)개의 팀에 대한 기록이 주어지면, 이 기록으로부터 팀 별 피타고라스 기댓값을 계산한 후, 그 중 최대 기댓값과 최소 기댓값을 출력하는 프로그램을 작성하시오.

입력 형식

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 줄에는 두 양의 정수 (n) (2 ≤ (n) ≤ 1,000)과 (m) (2 ≤ (m) ≤ 1,000)이 주어진다. 여기서, (n)은 팀 개수이며, (m)은 전체 경기 수이다. 다음의 (m)개의 줄에는 각 경기에 대한 정보가 주어진다. 하나의 경기는 네 개의 정수 (a), (b), (p), (q)로 주어지는데, 팀 a와 팀 b가 경기를 했고, 팀 a는 p득점을 팀 b는 q득점을 했다는 의미이다. 여기서, 1 ≤ (a) ≠ (b) ≤ (n)이며, (p)와 (q)는 모두 음이 아닌 20 이하의 정수이다. 하나의 테스트 데이터에서 팀 당 경기수가 반드시 같을 필요는 없다. 만약, 어떤 팀의 총 득점과 총 실점이 모두 0이라면, 그 팀의 기댓값은 0으로 정의한다.

출력 형식

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 두 정수 값을 한 줄에 하나씩 출력해야 한다. 첫 번째 줄에는 최대 피타고라스 기댓값에 1,000을 곱한 값의 정수부분을 출력하고, 두 번째 줄에는 최소 피타고라스 기댓값에 1,000을 곱한 값의 정수부분을 출력한다.

예제 입력

2
3 5
1 2 3 5
1 3 10 1
1 2 0 7
2 3 9 3
3 2 4 5
4 6
1 2 0 11
1 3 17 13
1 4 17 1
2 3 7 12
2 4 19 17
3 4 17 0

예제 출력

871
100
753
103