Отрезок и окружность

1000 мс · 256 МБ · всё или ничего

Сколько общих точек у отрезка и окружности?

Вопрос кажется мелким по сравнению с прямой и окружностью, но именно ограничение «отрезок, а не прямая» превращает его в аккуратную задачу.

Формат ввода

В первой строке - число запросов $q$ ( $1 \le q \le 10^5$ ).

В каждой из следующих $q$ строк - семь чисел: центр окружности, радиус, затем концы отрезка. Числа целые, по модулю не превосходят $10^4$ , радиус положителен. Концы отрезка могут совпадать.

Формат вывода

Для каждого запроса выведите число общих точек отрезка и окружности: 0, 1 или 2.

Примеры

ввод

3
0 0 5 -10 5 10 5
0 0 5 -10 0 10 0
0 0 5 0 0 1 1

вывод

1
2
0

ввод

2
0 0 5 3 4 3 4
0 0 5 0 0 0 0

вывод

1
0

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.