Вам дано два цілих числа (2 \le k < n).
Для масиву a_1, a_2, \ldots, a_n, який складається лише з нулів та одиниць, ми визначаємо масив наступним чином:
f(a)_i = a_i + a_{i+1} + \ldots + a_{i+k-2} + a_{i+k-1} (тут ми припускаємо, що a_{n + i} = a_i, тобто числа розташовані по колу).
Наприклад, для n = 4, k = 2, f([0, 1, 1, 0]) = [1, 2, 1, 0].
Розглянемо всі 2^n можливих масивів і для кожного з них знайдемо . Скільки серед них різних масивів? Оскільки відповідь може бути дуже великою, виведіть кількість цих масивів за модулем .
Два масиви вважаються різними, якщо вони відрізняються хоча б однією позицією.
Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість тестів. Нижче наведено опис тестових випадків.
Перший рядок кожного тесту містить два цілих числа (2 \le k < n \le 10^6).
Для кожного тесту виведіть кількість різних масивів серед за модулем .
Приклад 1
Для n = 3, k = 2 існує різних масивів одиниць і нулів. Відповідні масиви для них попарно різні.
Для n = 4, k = 2 існує різних масивів одиниць і нулів. Єдиною парою відповідних масивів є [0, 1, 0, 1] і [1, 0, 1, 0]: для обох масивів є [1 , 1, 1, 1].