Cerința

După ce Le. Quack a avut mare succes cu noul lui joc de cărți a decis să se apuce de scamatorii, pentru ca este pasionat de cărți îi cere patronului N cărți. Acesta așează toate cărțile pe față și se pregătește să facă o scamatorie. Acesta vrea să întoarcă toate cărțile pe spate, o operație constă în alegerea a mai multor cărți pe față adiacente și întoarcerea lor. Ca să facă totul mai interesant el alege Q persoane din public si acestea îi spun două numere, X Y, cu semnficația ca Le. Quack să facă toate trucurile posibile cu X cărți inițial pe față toate și exact Y operații de întoarcere astfel încât să ajungă cu toate cele X cărți alese pe spate. După fiecare dintre cele Q persoane el repune toate cărțile pe față. Le. Quack trebuie să numere toate posibilitățile de a face fiecare truc de magie doar că nu este bun la informatică așa că vă cere ajutorul!

Date de intrare

Fișierul de intrare flipc2.in conține pe prima linie numărul Q, iar pe următoarele Q linii câte 2 numere naturale separate prin spații cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire flipc2.out va conține pe prima Q linii răspunul aferent fiecărei întrebări din cele Q.

Restricții și precizări

• 1 ≤ Q ≤ 100.000.
• 1 <= Y <= X <= 1.000.000.
• Contează ordinea în care Le. Quack face operațiile.
• Rezultatul va fi tipărit modulo 100000469, care este un număr prim.

Exemplu:

flipc2.in

3
2 2
3 2
420 69

flipc2.out

2
4
45636278

Explicație

Pentru prima interogare el poate să învârtă cartea 1 iar apoi cartea 2 sau poate să învârtă cartea 2 apoi cartea 1.
Pentru interogarea 2, el poate întoarce cărțile 1 2 iar apoi cartea 3, poate întoarce cartea 3 apoi cărțile 1 2, poate să întoarcă cartea 1 iar apoi cărțile 2 3, în final poate să întoarcă cărțile 2 3 iar apoi cartea 1.
Pentru al treilea exemplu rezultatul este tipărit desigur modulo 100000469.