import math
def snt(n):
    if(n < 2):
        return False
    for i in range(2, int(n//2)+1):
        if(n%i == 0):
            return False
            break
    
    return True

n = int(input())

s = input()
a = s.split()

tmp = []

for i in a:
    if(snt(int(i))):
        tmp.append(int(i))

ok = [False for i in range(len(tmp))]

for i in range(len(tmp)):

    if(ok[i] == True):
        continue
    dem = 1
    for j in range(i + 1, len(tmp), 1):
        if(tmp[i] == tmp[j]):
            ok[j] = True
            dem += 1

    print(tmp[i], dem)
c0aa418b50fbb66e33c2ad109cd461c1d47056c8
<mask token>


def snt(n):
    if n < 2:
        return False
    for i in range(2, int(n // 2) + 1):
        if n % i == 0:
            return False
            break
    return True


<mask token>

<mask token>


def snt(n):
    if n < 2:
        return False
    for i in range(2, int(n // 2) + 1):
        if n % i == 0:
            return False
            break
    return True


<mask token>
for i in a:
    if snt(int(i)):
        tmp.append(int(i))
<mask token>
for i in range(len(tmp)):
    if ok[i] == True:
        continue
    dem = 1
    for j in range(i + 1, len(tmp), 1):
        if tmp[i] == tmp[j]:
            ok[j] = True
            dem += 1
    print(tmp[i], dem)

<mask token>


def snt(n):
    if n < 2:
        return False
    for i in range(2, int(n // 2) + 1):
        if n % i == 0:
            return False
            break
    return True


n = int(input())
s = input()
a = s.split()
tmp = []
for i in a:
    if snt(int(i)):
        tmp.append(int(i))
ok = [(False) for i in range(len(tmp))]
for i in range(len(tmp)):
    if ok[i] == True:
        continue
    dem = 1
    for j in range(i + 1, len(tmp), 1):
        if tmp[i] == tmp[j]:
            ok[j] = True
            dem += 1
    print(tmp[i], dem)

import math


def snt(n):
    if n < 2:
        return False
    for i in range(2, int(n // 2) + 1):
        if n % i == 0:
            return False
            break
    return True


n = int(input())
s = input()
a = s.split()
tmp = []
for i in a:
    if snt(int(i)):
        tmp.append(int(i))
ok = [(False) for i in range(len(tmp))]
for i in range(len(tmp)):
    if ok[i] == True:
        continue
    dem = 1
    for j in range(i + 1, len(tmp), 1):
        if tmp[i] == tmp[j]:
            ok[j] = True
            dem += 1
    print(tmp[i], dem)

import math
def snt(n):
    if(n < 2):
        return False
    for i in range(2, int(n//2)+1):
        if(n%i == 0):
            return False
            break
    
    return True

n = int(input())

s = input()
a = s.split()

tmp = []

for i in a:
    if(snt(int(i))):
        tmp.append(int(i))

ok = [False for i in range(len(tmp))]

for i in range(len(tmp)):

    if(ok[i] == True):
        continue
    dem = 1
    for j in range(i + 1, len(tmp), 1):
        if(tmp[i] == tmp[j]):
            ok[j] = True
            dem += 1

    print(tmp[i], dem)