ChthollyNotaSeniorious дает DataStructures числовую ось с \(m\) различными отрезками на ней. Пусть \(f(l,r)\) — количество способов выбрать четное число отрезков так, чтобы их объединение было равно \([l,r]\), а \(g(l,r)\) — количество способов выбрать нечетное число отрезков так, чтобы их объединение было равно \([l,r]\).
ChthollyNotaSeniorious задал DataStructures \(q\) вопросов. В каждом вопросе ChthollyNotaSeniorious дает DataStructures два числа \(l, r\), и хочет, чтобы вы помогли ему найти значение \(f(l,r)-g(l,r)\) по модулю \(998\,244\,353\), чтобы он не подвел ее.
Выходные данные
Для каждого запроса выведите одно целое число — \(f(l_i,r_i)-g(l_i,r_i)\) по модулю \(998\,244\,353\).
Примечание
В первом запросе мы должны найти \(f(1, 4) - g(1, 4)\). Единственное подмножество отрезков с объединением \([1, 4]\) это \(\{[1, 3], [2, 4]\}\), поэтому \(f(1, 4) = 1, g(1, 4) = 0\).
Во втором запросе нам нужно найти \(f(1, 5) - g(1, 5)\). Единственными подмножествами отрезков с объединением \([1, 5]\) являются \(\{[1, 3], [2, 4], [3, 5]\}\) и \(\{[1, 3], [3, 5]\}\), поэтому \(f(1, 5) = 1, g(1, 5) = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 3
4 6
2 4
3 5
1 4
1 5
|
1
0
|