Eğləncəli Say, Eğləncəli Deyil#12383
Sizə iki tam ədəd və verilir. Başlanğıc massiv [1, 2, 3, \dots, n] şəklində qurulur.
Massivin uzunluğu ən az olduğu müddətcə, aşağıdakı prosesi həyata keçirirsiniz:
Tam olaraq uzunluğunda istənilən bitişik alt massiv seçin.
Bu alt massivi -dan silin.
Qalan sol və sağ hissələri birləşdirərək yeni bir massiv yaradın.
Proses |A| < k olduqda başa çatır.
Proses dayandıqda mövcud ola biləcək fərqli massivlərin sayını müəyyən edin. Say böyük ola biləcəyi üçün nəticəni modulu ilə çıxarın.
İlk sətirdə bir tam ədəd (1 \le T \le 10^6) — test hallarının sayı.
Sonrakı sətirinin hər biri iki boşluqla ayrılmış tam ədəd və (1 \le n, k \le 10^6) ehtiva edir.
Hər test halı üçün, modulu ilə fərqli terminal massivlərin sayını təmsil edən bir tam ədəd çıxarın.
Nümunə 1
Alt tapşırıq ( xal): 1 \le n, k \le 10.
Alt tapşırıq ( xal): Bütün test hallarının \sum n \cdot k \le 10^6.
Alt tapşırıq ( xal): Bütün test hallarının \sum n \le 10^6.
Alt tapşırıq ( xal): bütün test hallarına eynidir.
Alt tapşırıq ( xal): Əlavə məhdudiyyət yoxdur.