У Jeevan есть два массива \(a\) и \(b\) размером \(n\). Он любит выполнять странные операции над массивами. На этот раз он придумал два типа операций:
- Выберите любое \(i\) (\(1 \le i \le n\)) и увеличьте \(a_j\) на \(1\) для каждого \(j\), которое кратно \(i\) и \(1 \le j \le n\).
- Выберите любое \(i\) (\(1 \le i \le n\)) и уменьшите \(a_j\) на \(1\) для каждого \(j\), которое кратно \(i\) и \(1 \le j \le n\).
Он хочет преобразовать массив \(a\) в массив \(b\), используя минимальное общее количество операций. Однако Jeevan, похоже, забыл значение \(b_1\). Поэтому он делает некоторые предположения. Он задаст вам \(q\) вопросов, соответствующих его \(q\) догадкам, \(i\)-я из которых имеет вид:
- Если \(b_1 = x_i\), то какое минимальное количество операций требуется для преобразования \(a\) в \(b\)?
Помогите ему, ответив на каждый вопрос.
Выходные данные
Выведите \(q\) целых чисел — ответы на каждый из его \(q\) вопросов.
Примечание
Рассмотрим первый пример.
- \(b_1 = 1\): Нам нужно преобразовать \([3, 7] \rightarrow [1, 5]\). Мы можем выполнить следующие операции:
\([3, 7]\) \(\xrightarrow[\text{уменьшить}]{\text{i = 1}}\) \([2, 6]\) \(\xrightarrow[\text{уменьшить}]{\text{i = 1}}\) \([1, 5]\) Следовательно, ответ равен \(2\).
- \(b_1 = 4\): Нам нужно преобразовать \([3, 7] \rightarrow [4, 5]\). Мы можем выполнить следующие операции:
\([3, 7]\) \(\xrightarrow[\text{уменьшить}]{\text{i = 2}}\) \([3, 6]\) \(\xrightarrow[\text{уменьшить}]{\text{i = 2}}\) \([3, 5]\) \(\xrightarrow[\text{увеличить}]{\text{i = 1}}\) \([4, 6]\) \(\xrightarrow[\text{уменьшить}]{\text{i = 2}}\) \([4, 5]\)
Следовательно, ответ — \(4\).
- \(b_1 = 3\): Нам нужно преобразовать \([3, 7] \rightarrow [3, 5]\). Мы можем выполнить следующие операции:
\([3, 7]\) \(\xrightarrow[\text{уменьшить}]{\text{i = 2}}\) \([3, 6]\) \(\xrightarrow[\text{уменьшить}]{\text{i = 2}}\) \([3, 5]\)
Следовательно, ответ равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 7
-1 5
3
1
4
3
|
2
4
2
|
|
2
|
6
2 5 4 1 3 6
-1 4 6 2 3 5
3
1
8
4
|
10
29
9
|