E. Деву и праздник день рождения
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Сегодня день рождения Деву. Чтобы отпраздновать это событие, он купил n конфет на рынке неподалеку и пригласил f своих друзей. Сейчас Деву хочет поделить конфеты между друзьями. Деву — добрый парень, и день сегодня особенный, так что он не хочет, чтобы кто-то грустил. Поэтому очень важно, чтобы каждый друг получил хотя бы одну конфету.

Юноша хочет, чтобы день рождения прошел особенным образом, поэтому конфеты требуется разделить по особенному. Предположим, что он раздал n сладостей своим друзьям так, что i-му другу досталось ai конфет. Не должно существовать ни одного целого числа x (x > 1), которое делит все ai.

Найдите количество способов распределения сладостей между друзьями, удовлетворяющих описанным ограничениям. Обратите внимание, что порядок имеет значение, например, [1, 2] и [2, 1] — различные распределения конфет. Так как ответ может быть достаточно велик, пожалуйста, выведите его по модулю 1000000007 (109 + 7).

Чтобы задача была еще интереснее, вам дано q запросов. Каждый запрос содержит пару n, f. Для каждого запроса выведите необходимое количество способов по модулю 1000000007 (109 + 7).

Входные данные

В первой строке записано целое число q, обозначающее количество запросов (1 ≤ q ≤ 105). В каждой из следующих q строк записано по два целых числа через пробел: n, f (1 ≤ f ≤ n ≤ 105).

Выходные данные

Для каждого запроса выведите единственное целое число в строке, соответствующее ответу на запрос.

Примеры
Входные данные
5
6 2
7 2
6 3
6 4
7 4
Выходные данные
2
6
9
10
20
Примечание

Для первого запроса: n = 6, f = 2. Возможные разделения: [1, 5] и [5, 1].

Для второго запроса: n = 7, f = 2. Возможные разделения: [1, 6] и [2, 5] и [3, 4] и [4, 3] и [5, 3] и [6, 1]. Таким образом, всего есть шесть возможных способов разделения.