A. Watching TV
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmed spends most of his day watching TV. His father noticed that his academic performance is degrading and decided to help him get back on track, for that he will allow him to choose only one frequency and watch the channels that share the same frequency band.

Can you help Ahmed choose the best frequency which is the one that displays the largest number of channels?

Input

The first line of the input contains an integer T (1  ≤  T  ≤  100), where T is the number of test cases. Then T test cases follow.

The first line of each test case contains an integer N (1  ≤  N  ≤  104), where N is the total number of channels.

Then N lines follow, each line contains a string S and an integer F (11111  ≤  F  ≤  99999), where S is the name of the channel and F is its frequency.

All strings are non-empty consisting of lowercase English letters. The length of each of these strings does not exceed 50 characters.

It is possible that two different channels have the same name and frequency.

Output

Print T lines, each line contains a single integer that represents the frequency Ahmed will choose. If there are several solutions, print the one with the minimum frequency.

Example
Input
3
3
mbcone 12015
mbctwo 12015
mbcthree 12014
2
channelone 11112
channelyou 21112
1
watchme 12345
Output
12015
11112
12345