def to_iobes():
  current = ''
  next_ = ''
  lines = stdin.readlines()
  for ind, line in enumerate(lines):
    if line != '\n':
      splitted = line.strip().split(' ')

      current = splitted[-1][0]
      new_current = ''
      next_ = lines[ind+1].strip().split(' ')[-1]
      if len(next_) > 0:
        next_ = next_[0]

      if current == 'B' and next_ == 'O':
        new_current = 'S'
      elif current == 'B' and next_ == 'B':
        new_current = 'S'
      elif current == 'I' and next_ == 'O':
        new_current = 'E'
      elif current == 'I' and next_ == 'B':
        new_current = 'E'
      elif current == 'B' and next_ == '':
        new_current = 'S'
      elif current == 'I' and next_ == '':
        new_current = 'E'
      else:
        new_current = current[0]
      splitted[-1] = new_current + splitted[-1][1:]

      joined = ' '.join(splitted)
    else:
      joined = ''
    print(joined)

def main():
    def bfs(initial, final):
        queue = deque([initial, None])
        count = 0
        while len(queue) > 1:
            node = queue.popleft()
            if node == final:
                break
            if node is None:
                count += 1
                queue.append(None)
                continue
            i, j = node
            for x, y in ((i - 1, j - 2),
                         (i - 2, j - 1),
                         (i - 2, j + 1),
                         (i - 1, j + 2),
                         (i + 1, j + 2),
                         (i + 2, j + 1),
                         (i + 2, j - 1),
                         (i + 1, j - 2)):
                if (0 <= x < 8) and (0 <= y < 8) and board[x][y]:
                    queue.append((x, y))
                    board[x][y] = False
        return count

    inp = stdin.readlines()
    for t in xrange(int(inp[0])):
        p1, p2 = inp[t + 1].split()
        board = [[True]*8 for _ in xrange(8)]
        print bfs(
            (ord(p1[0]) - ord('a'), int(p1[1]) - 1),
            (ord(p2[0]) - ord('a'), int(p2[1]) - 1))

def task():
    n = int(stdin.readline())
    counter = 0
    tree = defaultdict(list)
    words = []
    pattern = ''

    for index, value in enumerate(stdin.readlines()):
        if index < n - 1:
            parent_string, word = value.split()
            words.append(word)
            tree[int(parent_string) - 2].append(index)
        elif index == n - 1:
            pattern = value.strip()

    length = len(pattern)
    search = [(0, child) for child in tree[-1]]

    pi = compute_prefix_function(pattern)

    append, pop = search.append, search.pop
    while search:
        matchLen, index = pop()
        for c in words[index]:
            matchLen = pi[matchLen][c]
            if matchLen == length:
                counter += 1
        for child in tree[index]:
            append((matchLen, child))

    print counter

def main():
    p = ArgumentParser()
    p.add_argument("-s", dest="shell", action='store_true')
    p.add_argument("-n", "--no-raw", dest="accept_raw", action='store_false')
    args = p.parse_args()

    if args.shell:
        inputs = stdin.readlines()
        for i in inputs:
            try:
                cmd = handle_cmd(i, args.accept_raw)
            except Exception as e:
                dbg(e)
                raise
            if cmd:
                dbg("Executing %s" % cmd)
                c = Popen(cmd, shell=True, stdout=PIPE, stderr=PIPE)
                out, err = c.communicate()
                if c.returncode > 0:
                    call(["notify-send", "Error running: {}:\n{}".format(cmd,err)])
            else:
                dbg("Skipping unrecognized raw command '{}'".format(i))

    else:
        dmenu_path = Popen(["dmenu_path"], stdout=PIPE)
        # dmenu replacement, rofi
        # https://github.com/DaveDavenport/rofi
        dmenu = Popen(["rofi", "-dmenu"], stdin=dmenu_path.stdout, stdout=PIPE)
        #dmenu = Popen(["dmenu"], stdin=dmenu_path.stdout, stdout=PIPE)
        Popen([argv[0], "-s"], stdin=dmenu.stdout)

def main():
    import argparse
    from sys import exit, stdin
    parser = argparse.ArgumentParser()
    parser.add_argument('-v', '--version', action='version', version="%%(prog)s %s (%s)" % (__version__, __author__))
    parser.add_argument('username', help="Your HE DNS username")
    parser.add_argument('password', help="Your HE DNS password")
    parser.add_argument('command', nargs=argparse.REMAINDER,
                        help="An optional command, if blank we drop into interactive mode")
    options = parser.parse_args()

    shell = HurricaneDNSShell(options.username, options.password)
    try:
        if not options.command:
            if stdin.isatty():
                shell.cmdloop()
            else:
                for line in stdin.readlines():
                    shell.onecmd(line)
        else:
            from pipes import quote
            shell.onecmd(" ".join(map(lambda x: quote(x), options.command)))
    except HurricaneDNS.HurricaneAuthenticationError as e:
        print '%s: HE sent an error (%s)' % (parser.prog, e)
        exit(1)
    except HurricaneDNS.HurricaneError as e:
        print '%s: %s' % (parser.prog, e)

def main():
    from sys import stdin
    try:
        range = xrange
    except NameError:
        pass
    inp = iter(stdin.readlines())
    z = inp.next()
    while z != '0':
        x = 1
        dp = [0]*(len(z) + 1)
        dp[0] = 1
        dp[1] = 1
        lenz = len(z)
        if z[0] == '0':
            print(0)
            z = inp.next()
            continue
        for x in range(1, lenz):
            dp[x + 1] = dp[x]
            if z[x] == '0' and not ('1' <= z[x - 1] <= '2'):
                dp[lenz] = 0
                break
            elif z[x] == '0':
                continue
            if '10' <= z[x - 1:x + 1] <= '26':
                if x < lenz - 1 and z[x + 1] != '0':
                    dp[x + 1] += dp[x - 1]
                elif x == lenz - 1:
                    dp[x + 1] += dp[x - 1]
        print(dp[lenz])
        z = inp.next()

def mst():
	lines = stdin.readlines()
	n = len(lines)
	
    #Prims
	tagged = [0]*n
	heaviest = 0
	edges = 0
	
	heap = getNode(lines,0)
	heapify(heap)
	tagged[0] = 1
	
	while edges < n-1:
		edge = heappop(heap)
		target = edge[1]
		if tagged[target]:
			continue
		
		tagged[target] = 1
		if heaviest < edge[0]:
			heaviest = edge[0]
			
		for e in getNode(lines,target):
			if not tagged[e[1]]:
				heappush(heap, e)
		edges += 1

	return heaviest

def main():
	try:
		in_file = open(argv[1], 'r')
		try:
			data = [s.replace('\n', '') for s in in_file.readlines()]
		finally:
			in_file.close()
	except IOError:
		print("Cant open file or read data")
		data = [s.replace('\n', '') for s in stdin.readlines()]

	alphabet = data[0].split()
	k = len(alphabet)
	max_n = int(data[1])

	result_strings = []

	for n in range(1, max_n + 1):
		result_strings += get_all_numbers(alphabet, k, n)

	new_alphabet = dict(zip( alphabet, map(chr, range(65, 91)) ))

	result_strings = [(s, in_new_alphabet(s, new_alphabet)) for s in result_strings]

	result_strings.sort(key = lambda x: x[1])

	try:
		out_file = open("lexv_out.txt", 'w')
		try:
			for s in result_strings:
				print(s[0], file = out_file)
		finally:
			out_file.close()
	except IOError:
		print("Cant write data")

def main():
    lines = stdin.readlines()
    longest = max([len(t.rstrip()) for t in lines])

    for line in lines:
        left = len(line.rstrip()) - len(line.strip())
        print((line.strip()+(" "*left)).rjust(longest, " "))

	def read_input(self):
		print "Enter your statements(s) and then question(s). Terminate by pressing (Control + D) :"
		for line in stdin.readlines():
			self.lines.append( ((self.pattern.sub(' ',line)).strip()) )
			#self.lines.append(line)
		#print self.lines
		return self.lines

def main():
    from sys import stdin

    try:
        range = xrange
    except NameError:
        pass
    inp = iter(stdin.readlines())

    for x in range(int(inp.next())):
        # code...
        inp.next()
        a, plus, b, equ, c = inp.next().split()
        try:
            a = int(a)
        except ValueError:
            b = int(b)
            c = int(c)
            a = c-b
            print('{} {} {} {} {}'.format(a, plus, b, equ, c))
            continue
        try:
            b = int(b)
        except ValueError:
            c = int(c)
            b = c - a
            print('{} {} {} {} {}'.format(a, plus, b, equ, c))
            continue
        try:
            c = int(c)
        except ValueError:
            c = a + b
            print('{} {} {} {} {}'.format(a, plus, b, equ, c))
            continue

def main():
    lines = stdin.readlines()
    lines = [line.strip().split() for line in lines]
    true_pos = 0
    true_neg = 0
    false_pos = 0
    false_neg = 0
    for line in lines:
        pred = line[0]
        real = line[1]
        if real in POSITIVES and pred in POSITIVES:
            true_pos += 1
        elif real in POSITIVES and pred in NEGATIVES:
            true_neg += 1
        elif real in NEGATIVES and pred in POSITIVES:
            false_pos += 1
        elif real in NEGATIVES and pred in NEGATIVES:
            false_neg += 1
    
    soundness = float(true_pos)/(true_pos + true_neg)
    print "%f\tpercent of actual follow-backs predicted." % soundness*100
    completeness = float(true_pos)/(true_pos + false_pos)
    print "%f\tpercent of predicted follow-backs were correct." % completeness*100
    accuracy = float(true_pos + false_neg)/(true_pos + false_pos + true_neg + false_neg)
    print "%f\tpercent of all predictions were accurate." % accuracy*100

def main():
    inp = stdin.readlines()
    out = []
    for _ in range(int(inp[0])):
        a, b = inp[_ + 1].split()
        out.append(str(int(a[::-1]) + int(b[::-1]))[::-1].lstrip('0'))
    print('\n'.join(out))

def main():
    def maxarea(arr, length):
        stack = []
        i = 0
        max_area = float('-inf')
        while i < length:
            if len(stack) == 0 or arr[stack[-1]] <= arr[i]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                if stack:
                    area_with_top = arr[top] * (i - stack[-1] - 1)
                else:
                    area_with_top = arr[top] * i
                max_area = max(max_area, area_with_top)
        while stack:
            top = stack.pop()
            if stack:
                area_with_top = arr[top] * (i - stack[-1] - 1)
            else:
                area_with_top = arr[top] * i
            max_area = max(max_area, area_with_top)


        return max_area

    inp = stdin.readlines()
    inp.pop()
    for x in inp:
        l = map(int, x.split())
        length = l.pop(0)
        print maxarea(l, length)

def main():
    def maxpath(matrix, i, j):
        if i < 0 or i >= n or j < 0 or j >= m:
            return 0
        if memz[i][j]:
            return memz[i][j]
        # neighbour = (neigh_x, neigh_y)
        for neigh_x, neigh_y in zip(
                (i, i, i - 1, i + 1, i - 1, i - 1, i + 1, i + 1),
                (j - 1, j + 1, j, j, j - 1, j + 1, j - 1, j + 1)):
            if matrix[i][j] == matrix[neigh_x][neigh_y] - 1:
                memz[i][j] = max(memz[i][j], maxpath(matrix, neigh_x, neigh_y) + 1)

        return memz[i][j]

    inp = iter(stdin.readlines())
    n, m = map(int, inp.next().split())
    k = 1
    while n or m:
        mat = []
        memz = [[0]*52 for _ in xrange(52)]
        for x in xrange(n):
            mat.append(map(ord, list(inp.next())))
            mat[x].append(0)
            mat[x].append(0)
        mat.append([0] * (m + 2))
        ans = 0
        for x in xrange(n):
            for y in xrange(m):
                if mat[x][y] == 65:
                    ans = max(ans, maxpath(mat, x, y) + 1)
        print 'Case {}: {}'.format(k, ans)
        k += 1
        n, m = map(int, inp.next().split())

def main():
	from sys import stdin, stdout

	# stdin = open("input.txt", "r")

	inp = stdin.readlines()

	n = int(inp[0])

	versePattern = iter(map(int, inp[1].split()))

	ans = True

	for line in inp[2:]:
		vowelCnt = 0

		for x in line:
			if x in "aeiouy":
				vowelCnt += 1
	
		if vowelCnt != next(versePattern):
			ans = False
			break

	stdout.write("YES\n" if ans else "NO\n")

def main():
    """ Reads input from stdin, prints answer to stdout, and returns. """
    # Parse input
    lines = ''.join(stdin.readlines()).split('\n')
    splits = ( a.split(' ') for a in lines[1:] )    # generator
    parsed = [ (a[0], int(a[1])) for a in splits ]

    # Build lists 
    positive, negative = [], []
    for p in parsed:
        if p[1] > 0:
            positive.append(p)
        else:
            negative.append(p)

    # Find smaller list
    (smaller, larger) = (positive, negative) if len(positive) < len(negative) else (negative, positive)

    # Permute the smaller list
    for combo in combinations(smaller):
        calories = sum( a[1] for a in combo )
        for pcombo in combinations( [l for l in larger if abs(l[1]) < abs(calories)] ): # ignore elements with calorie count too big
            if sum( b[1] for b in pcombo ) + calories == 0:
                for ele in sorted( a[0] for a in combo+pcombo ):
                    print ele
                return 

    # No solution found
    print 'no solution'

def main():
    def extended_gcd(aa, bb):
        lastremainder, remainder = abs(aa), abs(bb)
        x, lastx, y, lasty = 0, 1, 1, 0
        while remainder:
            lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
            x, lastx = lastx - quotient * x, x
            y, lasty = lasty - quotient * y, y
        return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

    def modinv(a, m):
        g, x, _ = extended_gcd(a, m)
        if g != 1:
            raise ValueError
        return x % m

    inp = stdin.readlines()
    out = []
    for _ in xrange(int(inp[0])):
        n, p = map(int, inp[_ + 1].split())
        if n >= p:
            out.append("0")
            continue
        product = 1
        for x in xrange(p - 1, n, -1):
            product = (product * x) % p
        out.append(str(modinv(-1 * product, p)))

    print "\n".join(out)

def main():
    def steps(a, b, c):
        queue = deque([(0, 0), (-1, -1)])
        visited = set()
        count = 0
        while len(queue) > 1:
            x, y = queue.popleft()
            if x == -1 == y:
                count += 1
                queue.append((-1, -1))
                continue
            if x == c or y == c:
                return count
            if (x, y) in visited:
                continue
            visited.add((x, y))
            for p in [
                    (0, y), (x, 0), (a, y), (x, b),
                    (x - min(x, b - y), y + min(x, b - y)),
                    (x + min(y, a - x), y - min(y, a - x))]:
                if p not in visited and p != (x, y):
                    queue.append(p)
        return -1

    dstream = map(int, stdin.readlines())
    for t in xrange(dstream[0]):
        a, b, c = dstream[3*t + 1], dstream[3*t + 2], dstream[3*t + 3]
        print steps(a, b, c)

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)