আবির একজন স্কুলছাত্র। সে অঙ্ক করতে ভালবাসে। আর সে পাথর দিয়ে খেলতে পছন্দ করে। কিছুদিন আগে সে একটা নতুন খেলা আবিস্কার করেছে।
আবির এর কাছে অসংখ্য পাথর আছে। সে তার ভিতর থেকে N টি পাথর নিয়ে একটি বৃত্তে সাজায়। এরপর সে পাথরগুলোকে 1, 2, 3,.... N নাম্বার দিয়ে চিহ্নিত করে। বৃত্তের ভিতরে, প্রথম পাথর এর পরে দ্বিতীয় পাথর, তারপরে তৃতীয় পাথর, এভাবে সাজায় সে। পাথরগুলো বৃত্তাকারে সাজানো থাকায়, N তম পাথর এর পরে আবার প্রথম পাথর টি আছে। সে এই বৃত্তের নাম দিল মৃত্যুচক্র।
এখন সে তার মৃতুচক্র থেকে প্রতিটি দ্বিতীয় পাথর ফেলে দেয়, যতক্ষন পর্যন্ত না শুধুমাত্র একটা পাথর বাকি থাকে। উদাহরনস্বরূপ, সে যদি ৫ টি পাথর দিয়ে খেলা শুরু করে তাহলে, পাথর ফেলার ক্রম হবে এমনঃ সে প্রথম পাথরটি রেখে, দ্বিতীয় পাথরটি ফেলে দেয়। এরপর তৃতীয় পাথরটি রেখে চতুর্থ পাথরটি ফেলে দেয়। এরপর পঞ্চম পাথরটি রেখে প্রথম পাথরটি ফেলে দেয়। এভাবে খেলার পর, শুধুমাত্র তিন নাম্বার বা তৃতীয় পাথরটি বাকি ছিল। তাই এরপর সে তিনটি পাথর নিয়ে নতুন করে বৃত্তাকারে সাজাবে। এরপর আবার প্রতি দ্বিতীয় পাথরকে ফেলে। পাথর ফেলে দেয়ার ক্রম হচ্ছে এমনঃ 2->1। এবারো তৃতীয় পাথরটি বাদ যায়নি। যেহেতু সে তিনটি পাথর নিয়ে খেলা শুরু করেছিল, তাই সে সিদ্ধান্ত নেয় যে তিন হচ্ছে তার প্রিয় সংখ্যা।
সঠিকভাবে, সে প্রথমে N টি পাথর নিয়ে বৃত্তাকারে সাজায়। এরপর সে প্রতি দ্বিতীয় পাথর কে ফেলে দেয় যতক্ষন পর্যন্ত না শুধুমাত্র একটি পাথর বাকি থাকে। যদি x1 তম পাথরটি বাকি থাকে, তাহলে এরপর যদি x1 আর প্রথমে নেয়া পাথর এর সংখ্যা সমান হয়( এইখানে সংখ্যাটি হল N ), তাহলে সে খেলা বন্ধ করে দেয় আর সিদ্ধান্ত নেয় যে x হচ্ছে তার প্রিয় সংখ্যা। কিন্তু যদি x1 আর N সমান না হয়, তাহলে সে আবার x1 টা পাথর নিয়ে বৃত্তাকারে সাজায়, এবং প্রতি দ্বিতীয় পাথর কে ফেলে দেয়। এরপর, যদি x2 তম পাথরটি বাকি থাকে, তাহলে সে দেখে যে x1 = x2 নাকি। যদি সংখ্যা দুটি সমান হয়, তাহলে সে খেলা বন্ধ করে দেয় এবং সিদ্ধান্ত নেয় যে, x2
হচ্ছে তার প্রিয় সংখ্যা। যদি সংখ্যা দুটি সমান না হয়, তাহলে এভাবে খেলা চলতে থাকে। যখন xi টি পাথর নিয়ে খেলার পর xi তম পাথরটি বাকি থাকে, সে খেলা বন্ধ করে দেয়, আর সিদ্ধান্ত নেয় যে xi হচ্ছে তার প্রিয় সংখ্যা।
শুরুতে আবির N টি পাথর নিয়ে খেলা শুরু করে। সে খেলা শেষ হওয়ার পর সিদ্ধান্ত নেয় যে x তার প্রিয় সংখ্যা। তার প্রিয় বন্ধু নাবিল এটা দেখে সে ভাবল যে তার প্রিয় সংখ্যা ও x হতে হবে। তাই সে ভাবল, এমন কতগুলো পূর্ন সংখ্যা আছে 1 থেকে 2K - 1এর ভিতরে যেন, ওই সংখ্যা এর সমান পাথর নিয়ে খেলা শুরু করলে, প্রিয় সংখ্যা x হবে? তুমি কি তাকে সাহায্য করতে পারবে? যেহেতু উত্তর টি অনেক বড় হতে পারে, তাই একে 109 + 7 এর ভাগশেষ আকারে প্রকাশ করতে হবে।
ইনপুট এর প্রথম লাইন এ থাকবে T। এরপর T টি লাইন থাকবে। প্রতিটি লাইন এ দুটি পূর্ন সংখ্যা থাকবে। প্রথমটি N এর মান নির্দেশ করে এবং দ্বিতীয়টি K এর মান নির্দেশ করে।
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 1018
1 ≤ K ≤ 100000
সাবটাস্ক ১ (১০ পয়েন্টের জন্য)
1 ≤ T ≤ 5
1 ≤ N ≤ 50
1 ≤ K ≤ 5
সাবটাস্ক ২ (২০ পয়েন্টের জন্য)
1 ≤ T ≤ 10
1 ≤ N ≤ 1000000
1 ≤ K ≤ 5
সাবটাস্ক ৩ (৩০ পয়েন্টের জন্য)
1 ≤ T ≤ 5
1 ≤ N ≤ 10000000
1 ≤ K ≤ 20
সাবটাস্ক ৪ (৪০ পয়েন্টের জন্য)
আসল কন্সট্রেইন্টের জন্য।
প্রতিটি টেস্ট কেইস এর জন্য একটি লাইন আউটপুট দিবে। প্রতিটি N এবং K এর জন্য আউটপুট হবে 1 থেকে 2K - 1এর ভিতরে এমন কতগুলো পূর্ন সংখ্যা আছে, যেন ঐ সংখ্যা এর সমান পাথর নিয়ে খেলা শুরু করলে যে প্রিয় সংখ্যাটি পাওয়া যাবে, N টি পাথর দিয়ে খেলা শুরু করলে একই প্রিয় সংখ্যাটি পাওয়া যাবে। উত্তরটি 109 + 7 এর ভাগশেষ আকারে প্রকাশ করতে হবে
Input | Output |
---|---|
2 10 4 11 4 | 6 4 |