알고 있었는가, 사실 건공이는 굉장히 유능한 요리사라는 사실을. 건공이는 어떤 재료들을 받아도 가장 맛있는 음식을 만들어 낼 수 있는 엄청난 능력이 있다.</p>

건공이는 $1$번 재료부터 $N$번 재료까지 총 $N$개의 재료를 가지고 있다. 각 재료는 $T_i$의 맛 수치를 가진다. 건공이가 만드는 음식의 맛은 (사용한 모든 재료의 맛들을 XOR한 값 + 사용한 모든 재료의 개수)로 나타낼 수 있다.

$Q$개의 쿼리가 주어지고 각 쿼리마다 $l$과 $r$이 주어질 때, 각 쿼리에 대하여 $l$번째 재료부터 $r$번째 재료까지 ($r - l + 1$)개의 재료 중 $0$개 이상을 적절히 사용하여 만들 수 있는 요리의 맛 중 최댓값을 구하여라.

입력 형식

첫 번째 줄에 재료의 개수 $N$이 주어진다. ($ 1 \leq N \leq 500$)</p>

두 번째 줄에 $N$개의 재료의 맛 수치 $T_1, T_2, \cdots, T_N$이 공백으로 구분되어 주어진다. ($0 \leq T_i \leq 511$)

세 번째 줄에 쿼리의 개수 $Q$가 주어진다. ($1 \leq Q \leq 100\ 000$)

다음 $Q$개의 줄에 $l$과 $r$이 공백으로 구분되어 주어진다. ($1\leq l \leq r \leq N$)

출력 형식

$Q$개의 줄에 각 쿼리마다 건공이가 만들 수 있는 요리의 맛 중 최댓값을 한 줄씩 출력한다.

예제 입력

8
1 2 3 4 5 6 7 8
5
1 1
2 4
4 8
5 6
3 4

예제 출력

2
9
19
7
9