\textit{The Stirling number of the second kind} \textbf{S}(\textbf{n}, \textbf{m}) stands for the number of ways to partition a set of \textbf{n} things into \textbf{m }nonempty subsets. For example, there are seven ways to split a four-element set into two parts: \textbf{\{1, 2, 3\} U \{4\}, \{1, 2, 4\} U \{3\}, \{1, 3, 4\} U \{2\}, \{2, 3, 4\} U \{1\}} \textbf{\{1, 2\} U \{3, 4\}, \{1, 3\} U \{2, 4\}, \{1, 4\} U \{2, 3\}}. There is a recurrence which allows to compute \textbf{S}(\textbf{n}, \textbf{m}) for all \textbf{m} and \textbf{n}. \textbf{S(0, 0) = 1}; \textbf{S(n, 0) = 0} for \textbf{n} > \textbf{0}; \textbf{S(0, m) = 0} for \textbf{m} > \textbf{0}; \textbf{S(n, m) = mS(n - 1, m) + S(n - 1, m - 1)}, for \textbf{n}, \textbf{m} > \textbf{0}. Your task is much "easier". Given integers \textbf{n} and \textbf{m} satisfying \textbf{1} ≤ \textbf{m} ≤ \textbf{n}, compute the parity of \textbf{S(n, m)}, i.e. \textbf{S(n, m) mod 2}. Example,\textbf{ S(4, 2) mod 2 = 1}. Write a program which for each data set: \begin{itemize} \item reads two positive integers \textbf{n} and \textbf{m}, \item computes \textbf{S(n, m) mod 2}, \item writes the result. \end{itemize} \InputFile The first line of the input contains exactly one positive integer \textbf{d} equal to the number of data sets, \textbf{1} ≤ \textbf{d} ≤ \textbf{200}. The data sets follow. Line \textbf{i+1} contains the \textbf{i}-th data set - exactly two integers \textbf{n_i} and \textbf{m_i} separated by a single space, \textbf{1} ≤ \textbf{m_i} ≤ \textbf{n_i} ≤ \textbf{10^9}. \OutputFile The output should consist of exactly \textbf{d} lines, one line for each data set. Line \textbf{i}, \textbf{1} ≤ \textbf{i} ≤ \textbf{d}, should contain \textbf{0} or \textbf{1}, the value of \textbf{S(n_i, m_i) mod 2}.