Problem Statement
Little Chef doesn't love math anymore. He loves Aleksandra.


Sashen'ka is nice. They spend all the time together. Even their birthdays they are celebrating together, because they were born on the same day :)


And now, this day is coming...


Chef know that most of all Sasha loves numbers, that's why he bought N positive numbers to a girl.
From her side, Sasha as all girls, thought that if she likes something, then all people like that too. And bought to a boy N numbers too. xD
After all greeting young people decide to play a game with their gifts. The game will be continued for N turns, in each turn the following will be done:
Chef randomly choose some number x from his gift.
Sasha randomly choose some number y form her gift.
If x^y > y^x then girl will kiss fellow.
Numbers x,y will be discarded from gifts.
Now chef is wondering what is the expected number of times he will be kissed by Sasha ?

 

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of numbers in each gift. The second line contains N space-separated integers A1, A2, ..., AN denoting the numbers Sasha gave to Chef. Next line describe B1, B2, ..., BN numbers boy gave to girl in the same way. 
 

Output
For each test case, output a single line containing answer for corresponding test. Your answer will be considered as correct if it will have absolute error not more then 10^-6.
 

Constraints
1 ≤ T ≤ 5
1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^9
1 ≤ Bi ≤ 10^9
 

Example

Input
3
1
3
4
2
2 3
1 4
2
2 4
2 2

Output:
1.000000
1.500000
0.000000


 

Explanation
Example case 1. Game will have only 1 turn. Chef will choose 3, while Sasha will choose 4. Since 3^4>4^3 girl will kiss boy. Hence answer is 1.
import sys
from bisect import bisect_left


def line_to_array():
    return map(int, sys.stdin.readline().strip().split(' '))


def main():
    """
    x**y |          y*log(x) |                     log(x)/x |
         |--log-->           |--divide by (x*y)-->          |--> f(n) = log(n)/n
    y**x |          x*log(y) |                     log(y)/y |


    f(n)'s ascending interval: [1,3], descending interval: [3,inf]
    f_min = f(1)
    f_max = f(3)
    f(2) = f(4)
    """

    out = []
    num_test = line_to_array()[0]
    for i in range(num_test):
        counter = 0
        array_length = line_to_array()[0]
        chef_array = sorted(line_to_array())
        sasha_array = sorted(line_to_array())
        num_of_twos_in_chef = bisect_left(chef_array, 3) - bisect_left(chef_array, 2)
        num_of_threes_in_chef = bisect_left(chef_array, 4) - bisect_left(chef_array, 3)
        num_of_ones_in_sasha = bisect_left(sasha_array, 2)
        counter += num_of_twos_in_chef * (num_of_ones_in_sasha +
                                          array_length - bisect_left(sasha_array, 5))
        counter += num_of_threes_in_chef * (bisect_left(sasha_array, 3) +
                                            array_length - bisect_left(sasha_array, 4))
        for i in chef_array[bisect_left(chef_array, 4):]:
            counter += array_length - bisect_left(sasha_array, i + 1) + num_of_ones_in_sasha
        out.append(float(counter) / array_length)
    return out


if __name__ == "__main__":
    for i in main():
        print "%.6f" %i