Вова собирается поехать на конференцию на поезде. Изначально поезд находится в позиции \(1\), а пункт назначения — позиция \(L\). Скорость поезда равна \(1\) единице длины в минуту (то есть в первую минуту поезд находится в позиции \(1\), во вторую минуту — в позиции \(2\) и так далее).
Также на пути есть фонари. Они расположены в позициях с координатами, делящимися на \(v\) (то есть первый фонарь расположен в позиции \(v\), второй — в позиции \(2v\) и так далее).
Также на пути есть ровно один стоячий поезд, который занимает позиции от \(l\) до \(r\) включительно.
Вова может увидеть фонарь на позиции \(p\), если \(p\) делится на \(v\) и эту позицию не занимает стоячий поезд (\(p \not\in [l; r]\)). Таким образом, если точка, в которой есть фонарь, является одной из точек, принадлежащих стоячему поезду, Вова не сможет увидеть этот фонарь.
Ваша задача — сказать, какое количество фонарей Вова сможет увидеть во время своего пути. Вова собирается на \(t\) различных конференций, так что вам необходимо ответить на \(t\) независимых запросов.
Выходные данные
Выведите \(t\) строк. \(i\)-я строка должна содержать одно целое число — ответ на \(i\)-й запрос.
Примечание
Для первого тестового запроса ответ равен \(3\). Фонари находятся в позициях \(2\), \(4\), \(6\), \(8\) и \(10\), но Вова не видит фонари в позициях \(4\) и \(6\) из-за стоячего поезда.
Для второго тестового запроса ответ равен \(0\), потому что есть только один фонарь на позиции \(51\), но в этой позиции также находится стоячий поезд.
Для третьего тестового запроса ответ равен \(1134\), потому что всего есть \(1234\) фонарей, но Вова не может видеть фонари с позиции \(100\) по позицию \(199\) включительно.
Для четвертого тестового запроса ответ равен \(0\), потому что стоячий поезд покрывает весь путь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
10 2 3 7
100 51 51 51
1234 1 100 199
1000000000 1 1 1000000000
|
3
0
1134
0
|