def main():
    n = int(stdin.readline())
    nabomatrise = [None for i in xrange(n)]
    for i in xrange(n):
        nabomatrise[i] = [False] * n
        linje = stdin.readline()
        for j in xrange(n):
            nabomatrise[i][j] = (linje[j] == '1')
    for linje in stdin:
        start = int(linje)

        h_n = {start}
        utraversert = [start]

        while utraversert:
            rad = nabomatrise[utraversert.pop()]
            for i in xrange(n):
                if rad[i] and i not in h_n:
                    h_n.add(i)
                    utraversert.append(i)

        nrn = {i for i in xrange(n)} - h_n

        e = 0
        for node in nrn:
            row = nabomatrise[node]
            for i in xrange(n):
                if row[i] and i in nrn:
                    e += 1
        v = float(len(nrn))
        print "%.3f" % ((e / v**2 if v != 0 else 0) + 1E-12)

def read_emails_loop():
    from mftutor.settings import YEAR
    from sys import stdin
    while True:
        print('Enter student number:')
        studentnumber = stdin.readline().strip()
        if not studentnumber:
            print('Bye')
            break
        try:
            prof = TutorProfile.objects.get(studentnumber=studentnumber)
        except TutorProfile.DoesNotExist:
            print('Not found')
            continue
        print(prof)
        print(u'Groups: %s' %
              u', '.join(tg.name
                         for tg in TutorGroup.objects.filter(
                             tutor__profile=prof, tutor__year__exact=YEAR)
                         .order_by('-visible', 'name')))
        print(prof.email)
        print('Enter new email address:')
        email = stdin.readline().strip()
        if not email:
            print('No change')
            continue
        prof.email = email
        prof.save()
        print('Saved')

    def make_end_user_authorize_token(self, credentials, request_token):
        """Have the end-user authorize the token in their browser."""

        authorization_url = self.authorization_url(request_token)
        self.output(self.WAITING_FOR_USER % authorization_url)
        self.output(self.TIMEOUT_MESSAGE % self.TIMEOUT)
        # Wait a little time before attempting to launch browser,
        # give users the chance to press a key to skip it anyway.
        rlist, _, _ = select([stdin], [], [], self.TIMEOUT)
        if rlist:
            stdin.readline()
        self.output(self.WAITING_FOR_LAUNCHPAD)
        webbrowser.open(authorization_url)
        while credentials.access_token is None:
            time.sleep(access_token_poll_time)
            try:
                credentials.exchange_request_token_for_access_token(
                    self.web_root)
                break
            except HTTPError, e:
                if e.response.status == 403:
                    # The user decided not to authorize this
                    # application.
                    raise EndUserDeclinedAuthorization(e.content)
                elif e.response.status == 401:
                    # The user has not made a decision yet.
                    pass
                else:
                    # There was an error accessing the server.
                    print "Unexpected response from Launchpad:"
                    print e

def main():
    from sys import stdin

    maxint = 3500
    testcases = int(stdin.readline())
    for test in range(testcases):
        byer = int(stdin.readline())
        rekkefolge = map(int, stdin.readline().split())
        rekkefolge.append(rekkefolge[0])
        nabomatrise = [map(lambda x: maxint if x == '-1' else int(x), stdin.readline().split()) for _ in range(byer)]

        for k in range(byer):
            for i in range(byer):
                for j in range(byer):
                    nabomatrise[i][j] = min(nabomatrise[i][j], nabomatrise[i][k] + nabomatrise[k][j])
        rute = 0
        current = rekkefolge[0]
        umulig = False
        for by in rekkefolge[1:]:
            vei = nabomatrise[current][by]
            if vei == maxint:
                umulig = True
                break
            rute += vei
            current = by
        if umulig:
            print 'umulig'
        else:
            print rute

def main():
	T = int(raw_input())
	result = []
	if T == 0:
		result.append("NO")
	for i in range(0,T):
		
		array = []
		flag = 1
		result.append('NO')
		temp_result = 0

		n,k = map(int,stdin.readline().split())
		array.extend(stdin.readline().rstrip())
		[array.pop(array.index(x)) for x in array if x==' ']

		if len(array) > n:
			flag = 0
		if len(array) != len(set(array)):
			flag = 0
		
		for emnt in array:
			if ((int(emnt)%2 == 0 or k == 0) and int(emnt)!=0) and flag == 1:
				temp_result+=1 
				if temp_result >= k or k == 0:
					result[i] = "YES"
 				else: 
					result[i] = "NO"
			else:
				temp_result = 0
	for i in result:
		print i		

def mapper():
    t = None
    n = None
    line_errors = 0

    parse_line = re.compile('(\d+)\t(.*)')
    line = stdin.readline()
    while line:
        m = parse_line.match(line)
        if m:
            node = int(m.group(1))
            data = json.loads(m.group(2))
            # Do we have our metadata (load once)
            if not n:
                n = data['m'][0]
            if not t:
                t = data['m'][1]
                t_by_n = float(t) / n

            # Calculate our new PR
            data['p'] = t_by_n + (1 - t) * \
                sum(
                    i[1] / i[2] for i in data['s']
                )

            # Emit (with value pickled for size/efficiency)
            stdout.write("%s\t%s\n" %(node, json.dumps(data, 2)))
        else:
            line_errors += 1

        line = stdin.readline()

def main():
    from math import log
    from sys import stdin,stdout
    from itertools import tee 
    from functools import reduce
    def pairwise(iterable):    
        a, b = tee(iterable)
        next(b, None)
        return zip(a, b)   
    T = int(stdin.readline().strip())
    d = dict()
    while(T>0):
        N=int(stdin.readline().strip())
        L = set(map(int, stdin.readline().strip().split(' ')))
        if N==1: print("NO")
        else:
            sim = False
            key = ''
            for i in range(1,N+1):
                for a in pairwise(L):
                    key = ''.join(map(str,a))
                    if not d.__contains__(key):                              
                        r = reduce(lambda x,y: x&y,a)
                        if r>0 and log(r,2).is_integer(): 
                            sim = True                                                   
                            d[key]="YES"
                            break
                        else: d[key]="NO"
                    else: break                    
                if sim: break                
            stdout.write(d[key]+'\n')            
        T-=1

def main():
    setrecursionlimit(100000)
    # skapar en liten liten sköldpadda
    leonardo = Leonardo()
    q = LinkedQ()
    # stdin = open("firstsample.in")

    rad = stdin.readline()

    row = 1

    while rad:
        rad = rad.split("%", 1)[0] # Ta bort kommentarer.

        for tkn in rad.split():
            buildTokens(q, tkn, row)   # Lägg till tokens.

        row =row +1
        rad = stdin.readline() # Läs in ny rad.

    try:    # Skriv ut alla linjer
        match(q, leonardo)
        for i in range(0, len(leonardo.printout)): # Skriv ut allt när vi är klara.
            print(leonardo.printout[i])

    # Såvida det inte failar. Då skriver vi ut syntaxfel.
    except Syntaxfel as felet:
        print(felet)

def main():
    t = int(stdin.readline())
    while t > 0:
        t -= 1
        ans = 0
        n = int(stdin.readline())
        e = stdin.readline()
        e = list(e)
        x = stdin.readline().split()
        x = [int(i) for i in x]
        io = [i for i in range(0, n) if e[i] == '1']
        if len(io) == 1:
            ans = x[n - 1] - 1
        else:
            ans += 
            for i in range(0, len(io) - 1):
                if io[i] + 1 == io[i + 1]:
                    continue
                else:
                    minans = 32768
                    f = 0
                    for j in range(io[i], io[i + 1]):
                        d1 = x[j] - x[io[i]]
                        d2 = x[io[i + 1]] - x[j + 1]
                        f = d1 + d2
                        minans = min(f, minans)
                    ans += minans

        print ans

def main():
	case = 1
	while True:
		n, m = map(lambda x: int(x), stdin.readline().split())
		if n == 0:
			break
		names = []
		distance = [[1000 for j in range(n)] for i in range(n)]
		for x in range(n):
			distance[x][x] = 0
		for x in range(n):
			names.append(stdin.readline().strip())
		for x in range(m):
			i, j, k = map(lambda x: int(x), stdin.readline().split())
			i -= 1
			j -= 1
			distance[i][j] = distance[j][i] = k
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if distance[i][j] > (distance[i][k] + distance[k][j]):
						distance[i][j] = distance[i][k] + distance[k][j]
		min = 100000
		name = names[0]
		for i in range(n):
			s = sum(distance[i])
			if s < min:
				min = s
				name = names[i]
		print("Case #%d : %s" % (case, name))
		case += 1

def main ():
    line = stdin.readline()
    b = line.split()
    while b[0]!='0' and b[1]!='0'and b[2]!='0' and b[3]!='0':
        n=int(b[0])
        m=int(b[1])
        c=int(b[2])
        #print ("el c es: ", c)
        r=int(b[3])
        #print ("el r es: ", r)
        paint=[]
        mypaint=[]
        for j in range(n):
            l=[]
            l1 = stdin.readline() 
            l1=l1[:-1]
            lisnum=[]
            for t in l1:
                lisnum.append(int(t))
                l.append(0)
            paint.append(lisnum)
            mypaint.append(l)
        #imprimirpint(paint)
        print(solve(n,m,c,r,paint,mypaint))
        line = stdin.readline() 
        b = line.split()              

def main():
    print "Potential Plotter: {}".format(argv)
    if len(argv) == 5:
        r_min = float(argv[1])
        r_max = float(argv[2])
        th_min = float(argv[3])
        th_max = float(argv[4])
    elif len(argv) == 1:
        r_min = th_min = -30
        r_max = th_max = 30
    else:
        raise Exception('>>> ERROR! Please enter either zero or four parameters <<<')
    line = stdin.readline()
    ax1 = pyplot.figure().add_subplot(111)
    pyplot.grid(b=True, which='major', color='0.25', linestyle='-')
    ax1.set_xlabel('r, theta', color='0.20')
    ax1.set_ylabel('R(r)', color='b')
    ax1.set_ylim(r_min, r_max)
    ax2 = ax1.twinx()
    ax2.set_ylabel('THETA(theta)', color='r')
    ax2.set_ylim(th_min, th_max)
    n = 0
    while line:
        p = loads(line)
        ax1.plot(p['x'], p['R'], 'b.', markersize=2)
        ax2.plot(p['x'], p['THETA'], 'r.', markersize=2)
        line = stdin.readline()
        n += 1
    try:
        pyplot.show()
    except AttributeError as e:
        print('ATTRIBUTE ERROR: ' + str(argv[0]) + ': ' + str(e))
        exit(-1)

def main():
    print("Enter number of players")
    player_count = stdin.readline()

    all_actions = Coup.get_all_actions()  # general actions and character actions

    Coup.set_players(2)
    Coup.init_coup()

    print("Please enter the action you would like to take: 1-7")
    selection = stdin.readline()

    #  request block from the player who is targeted
    #  if no block is issued take the action
    #  if no challenge is issued take the action

    current_player = Coup.get_player_turn()

    #  check to see if action requires an affected player

    current_player.coins = 9
    if int(selection) in all_actions:
        influence = all_actions[int(selection)].effect(current_player, Coup.players[-1])
        Coup.remove_influence(Coup.players[-1], influence[-1])

        [print(c) for c in Coup.players[-1].influence]
    else:
        print("Invalid action chosen.")

    return

def main():
    db = pymongo.Connection().usenet
    print "Search movies without id:"
    s = stdin.readline()
    nzbs = [nzb for nzb in db.nzbs.find({'stages.movieid': {'$ne': True}, 'stages.uploaded': True, 'tags': '#[email protected]', 'rlsname': re.compile('%s' % s.rstrip(), re.I)})]
    for i in range(0, len(nzbs)):
        if 'error' in nzbs[i] and not nzbs[i]['error']['value'] in [421, 422, 423]: print 'ERROR', nzbs[i]['rlsname']; continue
        print str(i) + ':', nzbs[i]['rlsname']
        
    print
    while True:
        print 'Id movie: [num] [imdbid (ex. tt0123456)] or "exit"'
        s = stdin.readline()
        if s == 'exit\n': return
        m = re.match(r"(\d+)\s(tt\d{7})\n", s)
        m2 = re.match(r"^p\s+(\d+)\n", s)
        if m:
            i = int(m.group(1))
            nzb = nzbs[i]
            print 'Ided', nzb['rlsname'], 'as', 'http://www.imdb.com/title/' + m.group(2) + '/'
            print 'Are you sure (y/N)?'
            s = stdin.readline()
            if not s or not s[0] == 'y': continue
            del nzb['error']
            del nzb['stages']['error']
            nzb['link'] = 'http://www.imdb.com/title/' + m.group(2) + '/'
            nzb['movieid'] = m.group(2)
            nzb['stage'] = 3
            nzb['stages']['movieid'] = True
            db.nzbs.save(nzb)
            #print nzb
        elif m2:
            i = int(m2.group(1))
            nzb = nzbs[i]
            print nzb

def main():
    time0 = datetime.now()
    userinput = int(stdin.readline())
    while userinput!=0:
         if print_debug:
            print('\nInput = %s\n' % userinput)
         v = factorize(userinput)
         s = len(v)
         if s > 0:
             current = v[0]
             exp = 0
             it = 1
             for f in v:
                 if f == current:
                     exp += 1
                 else:
                     print('%d^%d' % (current, exp)),
                     current = f
                     exp = 1
                 if it == s:
                     print('%d^%d' % (current, exp))
                 it += 1
         userinput = int(stdin.readline())
    elapsed_time_function("main", time0)
    return 0

def main():
    T = int(stdin.readline())
    cases = []
    for t in range(T):
        bffs = map(int, stdin.readline().split())
        cases.append(bffs)
    solveAll(cases)

def main():
    syslog.openlog("update-hub-overlay", 0, syslog.LOG_LOCAL5)

    # get useful paths
    install_root = path.dirname(path.dirname(path.abspath(sys.argv[0])))
    opt_root = path.dirname(install_root)
    opt_inveneo = path.join(opt_root, "inveneo")

    stdout.write("\nUpdating: " + install_root + "...\n")
    svn_update(install_root)

    stdout.write("\nUpdating: " + opt_inveneo + "...\n")
    svn_update(opt_inveneo)

    stdout.write("\nInstalling any new packages...\n")
    sp.call([path.join(install_root, "bin", "install-packages.py"), path.join(install_root, "package.d")])

    stdout.write("\nReinstalling overlay...\n")
    sp.call([path.join(install_root, "bin", "install-hub-overlay.py")])

    stdout.write("\nRepopulating Samba...\n")
    sp.call([path.join(install_root, "bin", "populate-hub-ldap.py")])

    stdout.write("\nDone. Press enter/return key to reboot...\n")
    stdin.readline()
    os.system("reboot")

    return 0

def main():
    def sieve(n):
        numbers = [True]*n
        primes = []
        for x in range(2, n):
            if numbers[x]:
                primes.append(x)
                for y in range(2*x, n, x):
                    numbers[y] = False
        return primes

    primes = sieve(1001)
    stdin.readline()
    for n in map(int, stdin.readlines()):
        mc = float('-inf')
        for x in primes:
            if n == 1 or x >= n:
                break
            c = 0
            while n % x == 0:
                c += 1
                n /= x
            mc = max(c, mc)
        if n != 1:
            mc = max(1, mc)

        print(mc)

def main():
    from itertools import combinations
    from sys import stdin,stdout    
    def ch(n):
        c=0
        for i in range(len(n)-1):
            if n[i]==n[i+1]:
                c=1
                break
        if c==0:
            return True        
    s_len = int(stdin.readline().strip())
    s = stdin.readline().strip()
    l=list(s)
    n=list(set(l))
    if len(n)>=2:
        a=list(combinations(n,2))    
        m=[]    
        for i in a:
            s=''
            for j in l:
                if j in i:
                    s+=j
            m.append(s)        
        z=[]
        for i in m:
            if ch(i)==True:
                z.append(len(i))
        if len(z)>0:
            stdout.write(str(max(z))+'\n')
        else:
            stdout.write('0\n')
    else:
        stdout.write('0\n')

def task():
    try:
        count = int(stdin.readline())
        if count <= 0 or count > 1000:
            raise Exception("Invalid count")
        sessions = stdin.readline().split(' ')
        if count != len(sessions):
            raise Exception("Count doesn't match actual amount of sessions")

        one = set()
        two = set()
        for session in sessions:
            i = int(session)
            #print 'analyzing %s' % i
            if i == 0:
                #print 'skipping'
                continue
            if i in two:
                #print 'triple - raising exception'
                raise Exception("Conference is not allowed")
            if i in one:
                #print 'moving to two'
                one.remove(i)
                two.add(i)
            else:
                #print 'adding to one'
                one.add(i)

                #print 'one=%s\ntwo=%s' % (one, two)

        print len(two)
    except Exception, e:
        #print str(e)
        print -1