Task:

Pirates are swimming in the sea, which has n round islands. It is known that this gang is being sought by the English fleet. As you know, the power of the English fleet is very high, and it is easy for him to find pirates on the high seas. Pirates have found a way to hide from the English fleet: they drag their ship overland - the English fleet can’t find pirates on land.

Help the pirates find the way between the given islands, provided that the pirates’ ship’s time spent in the water should be minimal.

It is known that pirates are not the most literate people, that's why for pirates a unit of distance is equal to a unit of time.

Input:

The first line contains a natural n (1 ≤ n ≤ 100) – the quantity of islands.

The next n lines contain three numbers each – coordinates (x, y) of an island’s centre and its radius r.

The next line contains a natural m (1 ≤ m ≤ 1000) – the quantity of requests.

Each of m next lines contains two numbers: the number of the initial island (where pirates start their way) and the number of the final island, their destination point.

Output:

You should output the minimal time with 0.00001 accuracy for each of m requests, one number per one line.

Example: