URI Online Judge | 2735
# Nina's Gift

**Timelimit: 3**

By Giovanna Kobus Conrado, USP Brazil

Nina got **N** distinct** **numbers from 0 to N-1 for Christmas. She realized that those numbers can be used to form a permutation: an array of size **N** in which all numbers from 0 to N-1 appears once. She then remembered that she had kept a very special permutation of size **N **in her drawer, and she could use it to play with her new blocks. She came up with the following game:

At day 0, she will arrange the numbers in such a way that 0 is the fist one, 1 the second, and so on, until** N-1**, forming the array **V _{0}**. At day x, she will arrange the numbers to form the array

Her sister Nani got really jealous and decided to question Nina's knowledge about her permutation with questions of the following type: given two numbers **J** e **K**, what is the smallest number **Y **such that **V _{Y} [ ( J + K ) % N ] = J **?

Help Nina with her sister's questions.

The first line of input contains the number **t **(**t**=10) of test cases.

Each case starts with a line containing a number **N **(0<=**N**<=10^{5}): the number of blocks Nina got for Christmas. **N **distinct integers ranging from 0 to N-1 follow.

The next line will contain an integer **Q** (1<=**Q**<=10^{5}): the number of questions Nani will ask, followed by **Q** lines, each containing two integers **J** and **K **(0<=**J,K**<**N**).

For each question, print the answer. If it does not exist, print -1.

Input Sample | Output Sample |

1 5 2 0 1 4 3 3 0 2 2 0 2 1 |
2 0 -1 |