Sinister Aadi is in love with Interstellar. After watching Interstellar, he has decided to plan a game that will have very different winning conditions. He tries and comes up with an Odd/Even Game.
N people plays this game. Each with index 1..N. Each person gets a number A[i].
All the numbers that the people get are unique.
A person win a game with other persons in these conditions-
If the number that you have is even. Then you will win against all the persons who have an even value greater than it and odd value less than it. In any other case it will be a draw.
And if the number that you have is odd. Then you will win against all the persons who have an odd value greater than it and even value less than it. In any other case it will be a draw.

Now Sinister Aadi wants to know the probability of winning of a person with index I if the opponent is chosen randomly.

Input

The input file consists of several cases T (1<=T<=5).
The first line of each case contains a positive integer N (1<=N<=100000) specifying the number of players.
In next line there are N space separated values A[i..n] (1<=A[i]<=1000000) which is the number that the Ith person have.
In Next line there is Q i.e number of queries [1<=Q<=1000].       
In each query there will be an Index of a player. It 1-Based Indexing.

Output

For every query, you have to print the probability of the person winning with exactly 6 decimal digits.

Example

Input:
1
2
2 4
2
1
2

Output:
1.000000
0.000000