\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}.