Limits 1s, 512 MB

তোমাকে একটি N × N বর্গাকার দ্বিমাত্রিক গ্রিড বানাতে হবে মৌলিক সংখ্যা ঘুরিয়ে ঘুরিয়ে।
মৌলিক সংখ্যা হলো সেগুলো সংখ্যা যেগুলোকে ঐ সংখ্যা নিজে এবং ১ ছাড়া অন্য কোনো সংখ্যা দ্বারা নিঃশেষে বিভাজ্য করা যায় না (যেমনঃ ২, ৩, ৫, ৭, ১১ ইত্যাদি)
শুনতে জটিল মনে হচ্ছে? ছবি দিয়ে এইটা খুব সহজে বোঝানো সম্ভব।

N এর মান যদি ২ হয় তাহলে গ্রিডটা হবে এরকমঃ

N এর মান যদি ৩ হয় তাহলে গ্রিডটা হবে এরকমঃ

N এর মান যদি ৪ হয় তাহলে গ্রিডটা হবে এরকমঃ

এবং N এর মান বাড়ার সাথে সাথে এভাবেই চলতে থাকবে।

এখন তোমাকে N বলা হবে আর Q টা সেল নাম্বার দেওয়া হবে। বলতে হবে সেই সেলের মৌলিক সংখ্যাটি কত। যেমন ধরা যাক N যদি ২ হয় আর সেল নাম্বার হয় (২, ১) তাহলে সেই সেলের মৌলিক সংখ্যাটি হবে ২। আবার N যদি ৩ হয় আর সেল নাম্বার হয় (৩, ২) তাহলে সেই সেলের মৌলিক সংখ্যাটি হবে ১৯।

Input

প্রথম লাইনে বলা হবে N এবং Q। N নির্দেশ করে N × N গ্রিডের আকার আর Q নির্দেশ করে তোমাকে কতবার সেল নাম্বার জিজ্ঞেস করা হবে।
পরবর্তী Q সংখ্যক লাইনে তোমাকে দেওয়া হবে X এবং Y (1 ≤ X, Y ≤ N).
(X, Y) সেই সেল নাম্বারটি নির্দেশ করে।

১০ পয়েন্টের জন্য

  • 1 ≤ N ≤ 10
  • 1 ≤ Q ≤ 100

৩০ পয়েন্টের জন্য

  • 1 ≤ N ≤ 100
  • 1 ≤ Q ≤ 10000

৬০ পয়েন্টের জন্য

  • 1 ≤ N ≤ 1000
  • 1 ≤ Q ≤ 100000

Output

প্রত্যেক সেল নাম্বারের জন্য সেই সেলের মৌলিক সংখ্যাটি বলতে হবে।

Samples

InputOutput
3 2
1 3
2 1
5
13
InputOutput
4 3
1 2
4 1
4 4
47
17
29

Submit

Login to submit.

Statistics

84% Solution Ratio
Jarif_RahmanEarliest, Jun '20
nusuBotFastest, 0.1s
JoytunLightest, 9.1 MB
SIR.24Shortest, 965B
Toph uses cookies. By continuing you agree to our Cookie Policy.