Преследование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
kdivision.in
вывод
kdivision.out

Кецилий украл жезл Ватумба, и теперь Доктор Стрэндж преследует его по разным альтернативным реальностям. Буквально только что Доктор потерял его, но благодаря своим способностям он все еще может следить, где Кецилий сейчас находится.

Стрэндж записал все номера реальностей, в которых успел побывать Кецилий, и решил найти какую-нибудь закономерность его действий. Однако внезапно Доктор понял, что все номера он записал подряд без пропусков, и теперь невозможно точно восстановить номера реальностей.

Тем не менее Стивен запомнил три важных условия:

Точно восстановить передвижения злодея невозможно, поэтому сейчас Стрэндж хочет хотя бы знать количество способов разбить получившееся число на k других, чтобы выполнялись условия, описанные выше.

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

В первой строке содержится число t — количество тестов (1 ≤ t ≤ 100). В i-й из следующих t строк содержится описание i-го теста.

Тест описывается четырьмя числами x, l, r, k — числом, полученным Доктором Стрэнджем, границами для абсолютной разницы и количеством реальностей, в которых побывал Кецилий (1 ≤ x ≤ 1018, 0 ≤ l ≤ r ≤ 1018, 1 ≤ k ≤ 18).

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

На каждый тест в отдельной строке выведите ответ на него — искомое количество разбиений.

Пример

Входные данные
3
248 16 45 2
248 16 46 2
4444 1 5 2
Выходные данные
1
2
0

Примечание

В первом тесте возможно только одно разбиение, удовлетворяющее ограничениям на абсолютную разность: сначала Кецилий мог быть в реальности номер 24, а потом в реальности номер 8.

Во втором тесте возможны два разбиения: , .