Двійкові числа Стірлінга
Число Стірлінга другого роду S(n, m) дорівнює кількості способів розбиття множини з n елементів на m не порожніх підмножин. Наприклад, є сім способів розділити набір з чотирьох елементів на дві частини:
{1, 2, 3} U {4}, {1, 2, 4} U {3}, {1, 3, 4} U {2}, {2, 3, 4} U {1}
{1, 2} U {3, 4}, {1, 3} U {2, 4}, {1, 4} U {2, 3}.
Існує рекурентність, яка дозволяє обчислювати S(n, m) для усіх m і n.
S(0, 0) = 1; S(n, 0) = 0 для n > 0; S(0, m) = 0 для m > 0;
S(n, m) = mS(n - 1, m) + S(n - 1, m - 1), для n, m > 0.
Ваша задача значно "простіше". За заданими числам n та m, які задовольняють умові 1 ≤ m ≤ n, обчислити парність S(n, m), тобто S(n, m) mod 2.
Наприклад, S(4, 2) mod 2 = 1.
Напишіть програму, яка для кожного набору даних:
зчитує два натуральних n і m,
обчислює S(n, m) mod 2,
виводить результат.
Вхідні дані
У першому рядку вхідного файлу міститься рівно одне натуральне число d, рівне кількості наборів вхідних даних, 1 ≤ d ≤ 200. Далі йдуть самі набори вхідних даних.
Рядок i+1 містить i-й набір вхідних даних - рівно два цілих числа n_i та m_i відокремлених пропуском, 1 ≤ m_i ≤ n_i ≤ 10^9.
Вихідні дані
Вихідні дані повинні містити d рядків, по одному рядку для кожного набору вхідних даних. Рядок i, 1 ≤ i ≤ d, повинен містити 0 або 1, значення S(n_i, m_i) mod 2.