Masala #SZMXBAHELJ

Bir musobaqada $n$ ta ishtirokchi bor, har birining kuchi $s_i$ bo'lib, $(1 \leq s_i \leq n)$ va har bir ishtirokchining kuchi noyob (har bir o'yinchida faqat bitta noyob qiymat mavjud). Ishtirokchilar ikki jamoaga bo'linadi va ular o'yinni iloji boricha adolatli qilishni xohlaydi, shuning uchun ular jamoalarining kuchi teng bo'lishini istaydi. Biror jamoaning kuchi $(T)$ quyidagicha aniqlanadi:

Birinchi jamoaning kuchi va ikkinchi jamoaning kuchi o'rtasidagi minimal nisbatni aniqlang (Nisbat har doim butun son bo'lishini unutmang). Javob katta bo'lishi mumkin, shuning uchun uni $10^9 + 7$ ga bo'lganda chiqaring.
 

E'tibor bering, $(n=1)$ uchun javob 1 ga teng.

Birinchi qatorda bitta butun son $t$ $(1 \leq t \leq 10^4)$ — test holatlari soni.

Har bir test holatining yagona qatorida bitta butun son $n$ $(1 \leq n \leq 10^6)$ — ishtirokchilar soni.
 

Bu miqdor kafolatlangan $n$ oshmaydi $10^6$.

Bitta butun son, minimal nisbati $10^9 + 7$ moduli bo'yicha.