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