#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(m) for(int i=0; i<m; i++)
#define fro(m) for(int i=1; i<m; i++)
#define frj(m) for(int j=0; j<m; j++)
#define frr(n) for(int i=n; i>=0; i--)
#define pb push_back
#define pf push_front
#define orr ||
#define nl '\n'
#define nll cout<<'\n'
#define mod 1000000007
#define inf (1LL<<62)
#define inff (1<<30)
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define ff first
#define ss second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
int trie[ 300005 ] [ 100 ] , num, n;
int endshere[ 300005 ] ;
ll ans;
void init( ) {
memset ( trie,0 ,sizeof ( trie) ) ;
memset ( endshere,0 ,sizeof ( endshere) ) ;
num= 1 ;
}
void addElement( string s) {
int node= 1 ;
for ( char c : s) {
int ch= c- ' ' ;
if ( ! trie[ node] [ ch] ) trie[ node] [ ch] = ++ num;
node= trie[ node] [ ch] ;
}
endshere[ node] ++ ;
}
void traverse( int node, string s) {
if ( endshere[ node] ) {
cout << s<< " " ;
double ans= endshere[ node] * 100 ;
ans/ = n;
cout << setprecision( 4 ) << fixed<< ans<< nl;
}
fr( 91 ) {
if ( trie[ node] [ i] ) {
string s2= s;
char ch= ' ' + i;
s2.pb ( ch) ;
traverse( trie[ node] [ i] ,s2) ;
}
}
}
int main( )
{
fastio;
int t, cnt= 1 ;
cin >> t;
while ( t-- ) {
init( ) ;
string s;
if ( cnt) getline( cin ,s) , getline( cin ,s) ;
n= 0 ;
while ( getline( cin ,s) ) {
if ( s== "" ) break ;
n++ ;
addElement( s) ;
}
traverse( 1 ,"" ) ;
cnt= 0 ;
nll;
}
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGZyKG0pIGZvcihpbnQgaT0wOyBpPG07IGkrKykKI2RlZmluZSBmcm8obSkgZm9yKGludCBpPTE7IGk8bTsgaSsrKQojZGVmaW5lIGZyaihtKSBmb3IoaW50IGo9MDsgajxtOyBqKyspCiNkZWZpbmUgZnJyKG4pIGZvcihpbnQgaT1uOyBpPj0wOyBpLS0pCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgcGYgcHVzaF9mcm9udAojZGVmaW5lIG9yciB8fAojZGVmaW5lIG5sICdcbicKI2RlZmluZSBubGwgY291dDw8J1xuJwojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgaW5mICgxTEw8PDYyKQojZGVmaW5lIGluZmYgKDE8PDMwKQojZGVmaW5lIHllcyBjb3V0PDwiWUVTIjw8bmwKI2RlZmluZSBubyBjb3V0PDwiTk8iPDxubAojZGVmaW5lIGZmIGZpcnN0CiNkZWZpbmUgc3Mgc2Vjb25kCiNkZWZpbmUgZmFzdGlvIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKE5VTEwpCgppbnQgdHJpZVszMDAwMDVdWzEwMF0sIG51bSwgbjsKaW50IGVuZHNoZXJlWzMwMDAwNV07CmxsIGFuczsKCnZvaWQgaW5pdCgpewogICAgbWVtc2V0KHRyaWUsMCxzaXplb2YodHJpZSkpOwogICAgbWVtc2V0KGVuZHNoZXJlLDAsc2l6ZW9mKGVuZHNoZXJlKSk7CiAgICBudW09MTsKfQoKdm9pZCBhZGRFbGVtZW50KHN0cmluZyBzKXsKICAgIGludCBub2RlPTE7CiAgICBmb3IoY2hhciBjIDogcyl7CiAgICAgICAgaW50IGNoPWMtJyAnOwogICAgICAgIGlmKCF0cmllW25vZGVdW2NoXSkgdHJpZVtub2RlXVtjaF09KytudW07CiAgICAgICAgbm9kZT10cmllW25vZGVdW2NoXTsKICAgIH0KICAgIGVuZHNoZXJlW25vZGVdKys7Cn0KCnZvaWQgdHJhdmVyc2UoaW50IG5vZGUsIHN0cmluZyBzKXsKICAgIGlmKGVuZHNoZXJlW25vZGVdKXsKICAgICAgICBjb3V0PDxzPDwiICI7CiAgICAgICAgZG91YmxlIGFucz1lbmRzaGVyZVtub2RlXSoxMDA7CiAgICAgICAgYW5zLz1uOwogICAgICAgIGNvdXQ8PHNldHByZWNpc2lvbig0KTw8Zml4ZWQ8PGFuczw8bmw7CiAgICB9CiAgICBmcig5MSl7CiAgICAgICAgaWYodHJpZVtub2RlXVtpXSl7CiAgICAgICAgICAgIHN0cmluZyBzMj1zOwogICAgICAgICAgICBjaGFyIGNoPScgJytpOwogICAgICAgICAgICBzMi5wYihjaCk7CiAgICAgICAgICAgIHRyYXZlcnNlKHRyaWVbbm9kZV1baV0sczIpOwogICAgICAgIH0KICAgIH0KfQoKaW50IG1haW4oKQp7CiAgICBmYXN0aW87CiAgICBpbnQgdCwgY250PTE7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pewogICAgICAgIGluaXQoKTsKICAgICAgICBzdHJpbmcgczsKICAgICAgICBpZihjbnQpIGdldGxpbmUoY2luLHMpLCBnZXRsaW5lKGNpbixzKTsKICAgICAgICBuPTA7CiAgICAgICAgd2hpbGUoZ2V0bGluZShjaW4scykpewogICAgICAgICAgICBpZihzPT0iIikgYnJlYWs7CiAgICAgICAgICAgIG4rKzsKICAgICAgICAgICAgYWRkRWxlbWVudChzKTsKICAgICAgICB9CiAgICAgICAgdHJhdmVyc2UoMSwiIik7CiAgICAgICAgY250PTA7CiAgICAgICAgbmxsOwogICAgfQogICAgcmV0dXJuIDA7Cn0=
stdin
MQoKUmVkIEFsZGVyCkFzaApBc3BlbgpCYXNzd29vZApBc2gKQmVlY2gKWWVsbG93IEJpcmNoCkFzaApDaGVycnkKQ290dG9ud29vZApBc2gKQ3lwcmVzcwpSZWQgRWxtCkd1bQpIYWNrYmVycnkKV2hpdGUgT2FrCkhpY2tvcnkKUGVjYW4KSGFyZCBNYXBsZQpXaGl0ZSBPYWsKU29mdCBNYXBsZQpSZWQgT2FrClJlZCBPYWsKV2hpdGUgT2FrClBvcGxhbgpTYXNzYWZyYXMKU3ljYW1vcmUKQmxhY2sgV2FsbnV0CldpbGxvdwo=
1
Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow