Число Стирлинга второго рода 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.