Стірлінqin iki rəqəmli ədədləri
İkinci növ Stirling ədədi S(n, m), n elementdən ibarət çoxluğu m boş olmayan alt çoxluqlara bölmənin sayını göstərir. Məsələn, dörd elementdən ibarət dəsti iki hissəyə bölməyin yeddi yolu var:
{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}.
Bütün m və n üçün S(n, m) hesablanmasına imkan verən rekursiv bir əlaqə mövcuddur.
S(0, 0) = 1; S(n, 0) = 0 üçün n > 0; S(0, m) = 0 üçün m > 0;
S(n, m) = mS(n - 1, m) + S(n - 1, m - 1), üçün n, m > 0.
Sizin vəzifəniz daha "sadədir". Verilmiş n və m ədədləri üçün, şərti ödəyən 1 ≤ m ≤ n, S(n, m)-in cütlüyünü hesablamaq, yəni S(n, m) mod 2.
Məsələn, S(4, 2) mod 2 = 1.
Hər bir məlumat dəsti üçün proqram yazın:
iki təbii n və m oxuyur,
S(n, m) mod 2 hesablayır,
nəticəni çıxarır.
Giriş verilənləri
Giriş faylının ilk sətirində dəqiq bir təbii ədəd d var, bu, giriş məlumat dəstlərinin sayına bərabərdir, 1 ≤ d ≤ 200. Sonra giriş məlumat dəstləri gəlir.
Sətir i+1 i-ci giriş məlumat dəstini ehtiva edir - dəqiq iki tam ədəd n_i və m_i boşluqla ayrılmış, 1 ≤ m_i ≤ n_i ≤ 10^9.
Çıxış verilənləri
Çıxış məlumatları d sətir içərməlidir, hər bir giriş məlumat dəsti üçün bir sətir. Sətir i, 1 ≤ i ≤ d, 0 və ya 1, S(n_i, m_i) mod 2 dəyərini içərməlidir.