Запити про числа#7246
Етібар дуже любить числа. Тепер настав час вирішити нове завдання.
Дано натуральне число . Вам потрібно відповісти на запитів формату , де - тип запиту, а - натуральне число.
Якщо T = 1, знайдіть кількість натуральних чисел, які є одночасно дільниками і .
Якщо T = 2, знайдіть кількість натуральних чисел, які є дільниками і які діляться на .
Якщо T = 3, знайдіть кількість натуральних чисел, які є дільниками і які не діляться на .
Етібар може розв'язати всі ці запити, але якщо він це зробить, ви залишитеся голодними вночі, бо у нього не буде часу, щоб приготувати їжу. Тому ви домовилися, що кожен займатиметься своєю справою: ви програмуєте, а наш герой займається своїми справами.
Перший рядок містить числа: і (1 \le N \le 10^{12}, 1 \le Q \le 5 \cdot 10^5). Далі йдуть рядків, кожен з яких містить числа: і (1 \le T \le 3, 1 \le K \le 10^{12}).
Для кожного з запитів виведіть в окремому рядку відповідь на відповідний запит.
Приклад 1