Сегодня Денис проводит в ЛКШ клуб анонимных геометров. Он заготовил для клуба \(n\) выпуклых многоугольников, пронумерованных от \(1\) до \(n\). Он планирует предложить участникам клуба посчитать суммы Минковского этих многоугольников. А именно, он планирует дать \(q\) заданий, в \(i\)-м из них нужно посчитать сумму Минковского многоугольников с номерами от \(l_i\) до \(r_i\) включительно.
Суммой Минковского двух множеств \(A\) и \(B\) называется множество \(C = \{a + b : a \in A, b \in B\}\). Можно доказать, что если \(A\) и \(B\) являются выпуклыми многоугольниками, то \(C\) тоже будет выпуклым многоугольником.
Сумма двух выпуклых многоугольников Чтобы посчитать сумму Минковского \(p\) многоугольников (\(p > 2\)), нужно посчитать сумму Минковского первых \(p - 1\) многоугольников, а потом сумму Минковского результата и \(p\)-го многоугольника.
Для того, чтобы было удобнее проверять правильность выполнения заданий, Денис решил подготовиться и посчитать количество вершин в сумме Минковского для каждого задания. Помогите ему сделать это.
Выходные данные
Для каждого задания выведите одно целое число — количество вершин в сумме Минковского многоугольников с номерами от \(l_i\) до \(r_i\).
Примечание
Пояснение к примеру:
Первый, второй и третий многоугольники из тестового примера 
Суммы Минковского первого и второго, второго и третьего и всех трех многоугольников соответственно
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
0 0
1 0
0 1
4
1 1
1 2
0 2
0 1
3
2 2
1 2
2 1
3
1 2
2 3
1 3
|
5
5
6
|