동전 분배

윤화와 준희는 선생님께 받은 동전을 정확히 같은 금액으로 나누어 가지려 한다. 어느 한 사람이 1원이라도 더 받으면 둘 다 만족하지 못하므로, 두 사람이 받는 총액이 서로 같아야 한다.

동전은 자를 수 없으며, 자르면 더 이상 돈으로 쓸 수 없다. 따라서 각 동전은 한 사람에게 통째로 주어야 한다.

N가지 동전의 금액과 각 동전의 개수가 주어졌을 때, 모든 동전을 두 묶음으로 나누어 두 묶음의 총액을 같게 만들 수 있는지 판단하라.

세 개의 테스트 케이스가 연속해서 주어진다. 각 테스트 케이스의 첫 줄에는 동전 종류의 수 N (1 ≤ N ≤ 100)이 주어진다. 이어지는 N개의 줄에는 동전의 금액과 개수가 공백으로 구분되어 주어진다.

각 테스트 케이스에서 동전 금액의 총합은 100,000원을 넘지 않는다. 동전의 금액과 개수는 자연수이며, 같은 금액의 동전이 두 번 이상 주어지지 않는다.

세 줄을 출력한다. i번째 줄에는 i번째 테스트 케이스의 동전을 정확히 반으로 나눌 수 있으면 1, 없으면 0을 출력한다.