Задачі
Двійкові числа Стірлінга
Двійкові числа Стірлінга
\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}.
Вхідні дані #1
1 4 2
Вихідні дані #1
1