B. Эпический роман
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алекс купил новый роман, изданный в $$$n$$$ томах. Он прочитал все тома друг за другом, потратив на каждый несколько (один или более) полных дней. Другими словами, в первый день он читал первый том, и каждый следующий день он читал либо тоже самый том, что и днем ранее, либо следующий.

Пусть $$$v_i$$$ — это номер тома, который Алекс читал в $$$i$$$-й день. Ниже представлены некоторые примеры возможных ситуаций:

  • вполне возможна ситуация, что $$$v_1 = 1$$$, $$$v_2 = 1$$$, $$$v_3 = 2$$$, $$$v_4 = 3$$$, $$$v_5 = 3$$$. То есть Алекс потратил два дня ($$$1$$$-й и $$$2$$$-й) на первый том, один день ($$$3$$$-й) на второй том и два дня ($$$4$$$-й и $$$5$$$-й) на третий том;
  • ситуация $$$v_1 = 2$$$, $$$v_2 = 2$$$, $$$v_3 = 3$$$ невозможна, так как Алекс начал чтение с первого тома (таким образом, $$$v_1$$$ не может быть ни чем кроме $$$1$$$);
  • ситуация $$$v_1 = 1$$$, $$$v_2 = 2$$$, $$$v_3 = 3$$$, $$$v_4 = 1$$$ невозможна, так как Алекс не вернется к чтению первого тома после чтения третьего;
  • ситуация $$$v_1 = 1$$$, $$$v_2 = 3$$$ невозможна, так как Алекс не пропускает тома.

Вы знаете, что Алекс читал том $$$v_a$$$ в день $$$a$$$ и том $$$v_c$$$ в день $$$c$$$. Теперь вы хотите угадать, какой том он читал в день $$$b$$$, что находится между днями $$$a$$$ и $$$c$$$ (то есть, $$$a < b < c$$$). Возможно, однозначного ответа нет, а потому вас устроит любой подходящий по номеру том (т. е. выберете такое значение $$$v_b$$$, что возможна ситуация, когда Алекс читал том $$$v_a$$$ в день $$$a$$$, том $$$v_b$$$ в день $$$b$$$ и том $$$v_c$$$ в день $$$c$$$).

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

Во входных данных заданы несколько наборов входных данных. В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество томов, из которых состоит роман.

Во второй строке каждого набора заданы два целых числа $$$a$$$ и $$$v_a$$$ ($$$1 \le a \le 98$$$; $$$1 \le v_a \le a$$$) означающих, что Алекс читал том $$$v_a$$$ в день $$$a$$$.

В третьей строке каждого набора заданы два целых числа $$$c$$$ и $$$v_c$$$ ($$$a + 2 \le c \le 100$$$; $$$v_a \le v_c \le c$$$) означающих, что Алекс читал том $$$v_c$$$ в день $$$c$$$.

В четвертой строке каждого набора задано одно целое число $$$b$$$ ($$$a < b < c$$$) — интересующий вас день.

Гарантируется, что входные данные не противоречивы, то есть Алекс мог читать том $$$v_a$$$ в день $$$a$$$ и том $$$v_c$$$ в день $$$c$$$.

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

Для каждого набора входных данных, выведите номер тома, который Алекс мог читать в день $$$b$$$. Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
4
1
1 1
100 1
99
4
10 1
20 4
16
100
1 1
100 100
42
100
1 1
100 2
99
Выходные данные
1
2
42
1
Примечание

В первом наборе входных данных, так как Алекс читал том $$$1$$$ как в день $$$1$$$ так и в день $$$100$$$, то он совершенно точно читал том $$$1$$$ в любой другой день между ними.

Во втором наборе, Алекс мог читать любой том от $$$1$$$ по $$$4$$$ в день $$$16$$$. Например, он мог читать том $$$1$$$ со дня $$$1$$$ по день $$$15$$$, том $$$2$$$ в дни $$$16$$$ и $$$17$$$, том $$$3$$$ в день $$$18$$$ и том $$$4$$$ в дни $$$19$$$ и $$$20$$$.

В третьем наборе входных данных, возможна только одна ситуация: Алекс читал по тому в день, а потому в день $$$42$$$ он читал том $$$42$$$.