Coin Distribution

Yunhwa and Junhee want to divide the coins they received so that both people get exactly the same total value. If either person receives even 1 won more than the other, they will not be satisfied.

A coin cannot be cut. If it is cut, it loses its value as money, so each coin must be given whole to one of the two people.

Given N kinds of coins and the number of coins of each kind, determine whether all coins can be split into two groups with equal total value.

Three test cases are given consecutively. For each test case, the first line contains the number of coin kinds N (1 ≤ N ≤ 100). The next N lines each contain a coin value and the number of coins with that value, separated by a space.

For each test case, the total value of all coins does not exceed 100,000 won. Coin values and counts are positive integers, and the same coin value is not given more than once.

Print three lines. On the i-th line, print 1 if the coins in the i-th test case can be divided exactly in half, and print 0 otherwise.