BCS Mid Wales Programming Contest 2021

In simple ASCII images a dark pixel is represented as an asterisk * and a bright pixel as a full stop .

The darkness of an ASCII art image is defined as (number of * characters) / (number of characters in total).

Input

The first line of input contains the number of images. Subsequent lines of input contain either an integer defining the size of an "image", or image data.

All images are square, and the size of the image is the length of a side.

Output

For each input image, output the darkness of that image, one per line.

Example

Input:
2
2
..
.*
8
........
........
..*..*..
........
.*....*.
..****..
........
........

Output:
0.25
0.125