보석 분배

민혁이와 민규는 보석으로 가득찬 박스를 가지고 있고, 이제 이 보석을 나누려고 한다. 하지만, 각 보석의 가치가 다르기 때문에 공정하게 보석을 나누는 것은 매우 어려운 일이다.

보석을 나누기 위해서, 턴을 번갈아가면서 보석을 하나씩 가져간다. 보석이 남아있지 않을 때 까지 턴을 번갈아가며, 누가 먼저 시작할지는 동전을 던져서 결정한다.

민혁이와 민규는 서로 다른 전략을 가지고 보석을 고르려고 한다. 민혁이는 남아있는 보석 중에서 민혁이에게 가장 가치있는 보석을 고른다. 만약, 그러한 보석이 여러 가지라면, 민규에게 가장 가치가 없는 보석을 고른다.

민규는 최종 가치의 합이 최대가 되게 보석을 고른다. 만약, 그러한 보석이 여러 가지라면, 민혁이의 최종 가치가 최대한 크게 되는 보석을 고른다.

누가 턴을 먼저 시작할지와, 각 사람이 느끼는 보석의 가치가 주어졌을 때, 두 사람이 가져가는 보석의 가치를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 보석의 개수 n (1 ≤ n ≤ 1000)
• 먼저 턴을 시작하는 사람의 이름 (민혁이인 경우에는 "Petra", 민규인 경우에는 "Jan")
• n개의 줄에 걸쳐서 민혁이가 느끼는 가치 pi, 민규가 느끼는 가치 ji (0 ≤ pi, ji ≤ 1 000)

각 테스트 케이스에 대해서 두 사람이 최종적으로 가져가는 보석 가치를 출력한다.