Bakalavr təhsili alan#2846
Sasha, əvvəlki məsələdə qızın adını öyrənə bilmədiyi üçün soruşmaq qərarına gəldi, xoşbəxtlikdən yerli təhsil müəssisəsinin bazasına və populyar bir sosial şəbəkəyə çıxışı vardı. Məlum oldu ki, İra dörd il əlaçı olmuşdu və bakalavr dərəcəsi almaq əzmində idi. Sonra isə magistraturada və doktoranturada da oxumağı planlaşdırırdı. Kim bilir, sonra nə?
— Bəs bu, cəmdə nə qədər edəcək? — Sasha həvəslə düşündü, şüuraltı yaxında həll etmədiyi bir məsələnin üzərində düşünərək: iki ədəd və verilib, hesablayın
Birinci sətirdə (1 \le Q \le 41000) — sorğuların sayı verilir. Sonrakı sətirin hər birində iki ədəd (1 \le N \le 10^9) və (1 \le K \le 1000) verilir.
Hər bir sorğu üçün ayrıca sətirdə bir ədəd çıxış verin — -dən -ə qədər ədədlərin -cı qüvvətlərinin cəmini -yə bölünmüş qalığı ilə çıxışa yazın.
Nümunə 1