A. Множество Доры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Доры есть множество $$$s$$$, содержащее целые числа. Сначала она поместит все целые числа из отрезка $$$[l, r]$$$ в множество $$$s$$$. То есть, целое число $$$x$$$ изначально содержится в множестве тогда и только тогда, когда $$$l \leq x \leq r$$$. Затем она позволяет вам выполнять следующие операции:

  • Выберите три различных целых числа $$$a$$$, $$$b$$$ и $$$c$$$ из множества $$$s$$$, такие что $$$\gcd(a, b) = \gcd(b, c) = \gcd(a, c) = 1^\dagger$$$.
  • Затем удалите эти три целых числа из множества $$$s$$$.

Какое максимальное количество операций вы можете выполнить?

$$$^\dagger$$$Напомним, что $$$\gcd(x, y)$$$ означает наибольший общий делитель целых чисел $$$x$$$ и $$$y$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq 1000$$$) — диапазон целых чисел в начальном множестве.

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

Для каждого набора входных данных выведите одно целое число — максимальное количество операций, которые вы можете выполнить.

Пример
Входные данные
8
1 3
3 7
10 21
2 8
51 60
2 15
10 26
1 1000
Выходные данные
1
1
3
1
2
3
4
250
Примечание

В первом наборе входных данных вы можете выбрать $$$a = 1$$$, $$$b = 2$$$, $$$c = 3$$$ в единственной операции, так как $$$\gcd(1, 2) = \gcd(2, 3) = \gcd(1, 3) = 1$$$, в множестве больше нет целых чисел, поэтому больше операций выполнить нельзя.

Во втором наборе входных данных вы можете выбрать $$$a = 3$$$, $$$b = 5$$$, $$$c = 7$$$ в единственной операции.

В третьем наборе входных данных вы можете выбрать $$$a = 11$$$, $$$b = 19$$$, $$$c = 20$$$ в первой операции, $$$a = 13$$$, $$$b = 14$$$, $$$c = 15$$$ во второй операции и $$$a = 10$$$, $$$b = 17$$$, $$$c = 21$$$ в третьей операции. После трех операций множество $$$s$$$ содержит следующие целые числа: $$$12$$$, $$$16$$$, $$$18$$$. Можно доказать, что нельзя сделать больше $$$3$$$ операций.