COETEST5

Công ty X bí mật tổ chức một trò chơi để xem sự hiểu ý giữa các thành viên trong một bộ phận có cao hay không. Trò chơi có tên “Đoán ý đồng đội”.

Có N bộ phận trong công ty, để đơn giản các bộ phận được đánh số từ 1 đến N. Cách chơi như sau:

Ở mỗi lượt chơi, ban tổ chức sẽ bí mật gọi một người trong bộ phận thứ i lên để yêu cầu người đó cung cấp một con số (một người trong bộ phận được gọi lên duy nhất một lần). Sau đó, ban tổ chức sẽ tiên hành so sánh con số đó với các con số mà các nhân viên trong bộ phận thứ i đã cung cấp trước đó. Nếu có một sự trùng lặp thì đội thứ i sẽ được cộng thêm 1 điểm.

Cho N bộ phận, M lượt chơi và các thông tin của một lượt chơi bao gồm: số thứ tự của bộ phận và con số mà một nhân viên bộ phận đó cung cấp. Hãy xác định bộ phận nào có điểm số cao nhất.

[Ví dụ]

Dưới đây là 10 lượt chơi của bộ phận số 1:

• Ở lượt chơi thứ 4, nhân viên cung cấp số 12345 cho ban tổ chức. Sau khi ban tổ chức tiến hành so sánh thì thấy con số này trùng lặp với con số ở lượt chơi thứ 1 nên bộ phận số 1 được cộng 1 điểm.
• Ở lượt chơi thứ 8, nhân viên cung cấp số 521935 cho ban tổ chức. Sau khi ban tổ chức tiến hành so sánh thì thấy con số này trùng lặp với con số ở lượt chơi thứ 3 nên bộ phận số 1 được cộng 1 điểm.
• Ở lượt chơi thứ 10, nhân viên cung cấp số 12345 cho ban tổ chức. Sau khi ban tổ chức tiến hành so sánh thì thấy con số này trùng lặp với con số ở lượt chơi thứ 4 và lượt chơi thứ nhất nên bộ phận số 1 được cộng 2 điểm.

Như vậy, sau 10 lượt chơi, đội số 1 có 4 điểm.

[Input]

Dòng đầu tiên là số lượng test case T (T ≤ 50). Thông tin về mỗi test case như sau:

Mỗi test case được cho trên M + 1 dòng:

Dòng đầu tiên là hai số nguyên dương N (1 ≤ N ≤ 1.000) và M (1 ≤ M ≤ 20.000), trong đó N là số bộ phận của công ty, M là tổng số lượt chơi.

M dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương x (1 ≤ x ≤ N) và y (1 ≤ y ≤ 1.000.000.000), trong đó x là số thứ tự của bộ phận, y là con số mà nhân viên trong bộ phận thứ x cung cấp cho ban tổ chức.

Lưu ý, trong mỗi test case, mỗi bộ phận sẽ không có quá 100 nhân viên.

[Output]

Đưa ra output trên T dòng tương ứng với T test case.

Mỗi test case in ra “#tc” với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra bao gồm 2 số phân biệt nhau bởi dấu cách, số thứ nhất là số thứ tự của bộ phận được điểm cao nhất và số thứ hai là số điểm của bộ phận đó. Trường hợp nếu có nhiều bộ phận bằng điểm nhau, in ra bộ phận có số thứ tự là lớn nhất.

Example

Input:
3
3
3 20
2 12345
1 12345
1 867831
2 634634
3 4636546
1 521935
2 534523
3 452364
1 12345
2 53453
1 357845
1 123456
1 613466
3 534523
3 523454
1 521935
1 21521
2 456346
1 12345
3 2359571
6 22
4 15504721
6 6288245
6 6288245
3 1296709
4 8602647
6 6288245
6 995457
2 8602647
6 11687041
2 7784401
6 8645445
6 15457407
4 2944129
5 4155557
5 1190063
6 15157561
5 529256
4 21015826
4 2891476
5 529256
3 20569729
1 1190063
10 122
3 3287461
9 5670115
2 11550603
10 6032476
5 2656301
1 9163419
7 14353741
2 3116305
4 2637857
10 11424493
5 2656301
6 188101
9 8893561
8 2555725
4 2637857
3 3287461
3 12151945
3 657647
3 8195041
6 63657
9 8893561
9 6534016
6 11114287
2 6622793
8 2555725
3 3287461
3 5355780
6 11114287
4 911905
8 489901
1 4201637
1 13804363
2 784824
7 14353741
10 6283916
4 415811
10 11424493
2 15379401
9 14172894
5 3687142
7 12451076
4 911905
9 2477837
3 13189315
3 12107233
5 2656301
3 15848880
10 4071591
7 1357897
4 911905
2 3116305
1 2177956
1 23344601
6 6097071
5 1001385
1 4364515
2 1357897
3 2931556
8 221320
6 11114287
3 24895233
4 911905
6 4410979
4 911905
2 2082145
5 2103155
10 6283916
3 25883649
2 14366241
2 4152931
9 14172894
1 13014453
1 87193
2 1746002
2 21826641
8 6989827
10 3667977
6 1391131
5 2519917
1 15862816
7 11124401
5 5471831
1 2800297
10 11424493
8 20798401
2 1746002
1 2212561
4 911905
3 2931556
5 8357713
4 8111665
8 8579606
10 760126
3 15848880
1 20531589
3 15848880
2 3571841
8 20798401
7 1835692
8 8579606
5 24858019
9 6534016
7 15442801
5 2626297
6 9123301
5 1949965
8 5130217
1 11557727
6 4410979
7 6394623
5 1152373
4 530011
7 2789595
2 2132131
1 11557727
8 16638859
3 1162877
4 3749005
9 6534016
7 9186541
10 524857
2 3601033

Output:
#1 1 4
#2 6 3
#3 4 16