\textit{Число Стирлинга второго рода} \textbf{S}(\textbf{n}, \textbf{m}) равно количеству способов разбиения множества из \textbf{n} элементов на \textbf{m }непустых подмножеств. Например, есть семь способов разделить набор из четырёх элементов на две части: \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\}}. Существует рекурентность, которая позволяет вычислять \textbf{S}(\textbf{n}, \textbf{m}) для всех \textbf{m} и \textbf{n}. \textbf{S(0, 0) = 1}; \textbf{S(n, 0) = 0} для \textbf{n} > \textbf{0}; \textbf{S(0, m) = 0} для \textbf{m} > \textbf{0}; \textbf{S(n, m) = mS(n - 1, m) + S(n - 1, m - 1)}, для \textbf{n}, \textbf{m} > \textbf{0}. Ваша задача значительно "проще". По заданным числам \textbf{n} и \textbf{m}, удовлетворяющих условию \textbf{1} ≤ \textbf{m} ≤ \textbf{n}, вычислить чётность \textbf{S(n, m)}, то есть \textbf{S(n, m) mod 2}. Например,\textbf{ S(4, 2) mod 2 = 1}. Напишите программу, которая для каждого набора данных: \begin{itemize} \item считывает два натуральных \textbf{n} и \textbf{m}, \item вычисляет \textbf{S(n, m) mod 2}, \item выводит результат. \end{itemize} \InputFile В первой строке входного файла содержится ровно одно натуральное число \textbf{d}, равное количеству наборов входных данных, \textbf{1} ≤ \textbf{d} ≤ \textbf{200}. Далее следуют сами наборы входных данных. Строка \textbf{i+1} содержит \textbf{i}-й набор входных данных - ровно два целых числа \textbf{n_i} и \textbf{m_i} разделённых пробелом, \textbf{1} ≤ \textbf{m_i} ≤ \textbf{n_i} ≤ \textbf{10^9}. \OutputFile Выходные данные должны состоять из \textbf{d} строк, по одной строке для каждого набора входных данных. Строка \textbf{i}, \textbf{1} ≤ \textbf{i} ≤ \textbf{d}, должна содержать \textbf{0} или \textbf{1}, значение \textbf{S(n_i, m_i) mod 2}.