amicable-numbers

Amicable numbers

medium

تسمى الأعداد الطبيعية \(A\) و\(B\) أعدادًا صديقة إذا كان \(B\) مساويًا لمجموع جميع القواسم الصحيحة لـ \(A\) ما عدا \(A\) نفسه، و\(A\) مساويًا لمجموع جميع القواسم الصحيحة لـ \(B\) ما عدا \(B\) نفسه.

على سبيل المثال، الأعداد 220 و284 هي أعداد صديقة.

لديك عدد طبيعي \(M\) و\(M\) استعلامًا. كل استعلام يحتوي على عدد \(n_i\). لكل استعلام، أجب: كم عدد أزواج الأعداد الصديقة موجودة بحيث لا يزيد أي عدد في الزوج عن \(n_i\)؟

المدخلات:

السطر الأول يحتوي على العدد الطبيعي \(M\).
الأسطر التالية \(M\) تحتوي كل منها على عدد طبيعي \(n_i\).

المخرجات:

لكل استعلام، اطبع عدد أزواج الأعداد الصديقة في سطر جديد.

المحددات:

\(1 \leq M \leq 10^5\)
\(1 \leq n \leq 10^5\)

إذا كانت هذه المسألة صعبة جدًا عليك، فحاول حلّها عندما

\(m = 1\) و\(n \leq 10^5\)

أو، إذا كانت لا تزال صعبة جدًا، فحاول حلّها عندما

\(m = 1\) و\(n \leq 3000\)

مثال:

مدخل:

1
2700

مخرج: