Өнөөдөр бол Дэвүгийн төрсөн өдөр. Тэр төрсөн өдрийн үдэшлэгтээ зориулж ойролцоох дэлгүүрээс $n$ амттан худадаж аваад $f$ найзыгаа урив. Дэвү найзуудынхаа дунд амттан тараахыг хүсэж байв. Тэр сайн залуу ба үйл явдлыг гайхалтай, ямар ч найзыгаа гунигтай байлгахыг хүсэхгүй байгаа учраас хүн бүрт дор хаяж нэг амттан өгөхийг хүсэж байв.

Тэр үдэшлэгийг онцгой байлгахыг хүсэж байгаа учраас амттан тараахдаа дараах нөхцөлийг тавина. $n$ амттанг тараахдаа $i$-р найздаа $a_{i}$ амттан өгсөн гэж бодъё. Тэр ямар ч эерэг бүхэл $x > 1$ нь $a_{i}$ бүрийг хуваадаг байх ёсгүй гэж хүссэн.

Тавьсан шаардлагынхаа дагуу найзууддаа амттан тараах арга замын тоог олоход нь туслана уу. Хувиарлалтыг цэгцтэй хийх нь чухал, жишээ нь [1, 2] ба [2, 1] нь ялгаатай хувиарлалт гэдгийг анхаарна уу. Хариулт нь маш их тоо байж болох ба $1000000007$ $(10^{9} + 7)$ модулиар гаргасан байна. Асуудлыг илүү сонирхолтой болгохын тулд чамд $q$ асуултууд өгсөн байна. Асуулт бүр нь $n$, $f$ хос тоо агуулна. Асуулт бүрийн шаардагдсан тоог $1000000007$ $(10^{9} + 7)$ модулиар гаргана.

Оролт

Эхний мөрөнд асуултуудын тоог илэрхийлсэн $q$ $(1 ≤ q ≤ 10^{5})$ бүхэл тоо байна. Дараагийн $q$ мөр бүр нь таслалаар тусгаарлагдсан $n$, $f$ $(1 ≤ f ≤ n ≤ 10^{5})$ хоёр бүхэл тоог агуулна.

Гаралт

Асуулт бүрийн хариуг харгалзуулан нэг мөрөнд хэвлэнэ.

Энхний асуултын: $n = 6, f = 2$. Боломжит хуваалтууд нь [1, 5] ба [5, 1].

Хоёр дахь асуулт: $n = 7, f = 2$. Боломжит хуваалтууд нь [1, 6], [2, 5], [3, 4], [4, 3], [5, 3], [6, 1]. Ийм 6 аргаар хуваана.