Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на большую степень числа 2. 

По заданной последовательности целых положительных чисел a_1, a_2, ..., a_{n} требуется найти r — максимальную степень числа 2, на которую делится хотя бы одно из чисел последовательности. Кроме того, требуется вывести количество чисел a_{i}, которые делятся на r.


-----Входные данные-----

В первой строке записано целое число n (1 ≤ n ≤ 100) — длина последовательности a.

Во второй строке записана последовательность целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Выходные данные-----

Выведите два числа:

  r — максимальную степень двойки, на которую делится хотя бы одно из чисел заданной последовательности,  количество элементов последовательности, которые делятся на r. 


-----Примеры-----
Входные данные
5
80 7 16 4 48

Выходные данные
16 3

Входные данные
4
21 5 3 33

Выходные данные
1 4



-----Примечание-----

В первом тестовом примере максимальная степень двойки, на которую делится хотя бы одно число, равна 16 = 2^4, на неё делятся числа 80, 16 и 48.

Во втором тестовом примере все четыре числа нечётные, поэтому делятся только на 1 = 2^0. Это и будет максимальной степенью двойки для данного примера.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
l = list(map(int, input().split()))
max1 = 1
for i in l:
    k = 1
    x = i
    while x % 2 == 0:
        k *= 2
        x //= 2
    max1 = max(max1, k)
c = 0
for i in l:
    if i % max1 == 0:
        c += 1
print(max1, c)

n = int(input())
a = list(map(int, input().split()))
pw = [0] * 40
for i in a:
	x = 1
	pos = 0
	while i % x == 0:
		pw[pos] += 1
		pos += 1
		x *= 2
for i in range(39, -1, -1):
	if pw[i] != 0:
		print(2 ** i, pw[i])
		break

read = lambda: list(map(int, input().split()))
n = int(input())
a = list(read())
ans = -1
cnt = 0
for i in range(n):
    r = 0
    while a[i] % (2 ** r) == 0:
        r += 1
    r -= 1
    if r > ans:
        ans = r
        cnt = 1
    elif r == ans:
        cnt += 1
print(2 ** ans, cnt)
               


import sys
n=int(input())
z=list(map(int,input().split()))
max_=0
for i in range(n):
    f=z[i]
    ctr=0
    while True:
        if f%2==0:
            f//=2
            ctr+=1
        else:
            break
    max_=max(max_,ctr)
print(2**max_,end=' ')
ctr=0
f=2**max_
for i in range(n):
    if z[i]%f==0:
        ctr+=1
print(ctr)

from math import log2
def c(a, b):
    for i in a:
        if i % b == 0:
            return True
    return False
def cnt(a, b):
    ans = 0
    for i in a:
        if i % b == 0:
            ans += 1
    return ans
input()
a = [int(i) for i in input().split()]
b = 2
while c(a, b):
    b *= 2
print(b // 2, cnt(a, b // 2))

n = input()
cur = 0
cnt = 0
for i in map(int, input().split()):
    c = 0
    while i % 2 == 0:
        i >>= 1
        c += 1
    if c > cur:
        cur = c
        cnt = 1
    elif c == cur:
        cnt += 1
print(2 ** cur, cnt)

n=int(input())
a=list(map(int,input().split()))
ma=0
for i in range(n):
    s=a[i]
    st=1
    while s!=1:
        if s%2==0:
            s//=2
            st*=2
        else:
            break
    if st>ma:
        ma=st
v=0
for i in range(n):
    if a[i]%ma==0:
        v+=1
print(ma,v)



n = int(input())
a = list(map(int, input().split()))
r = 0
k = 0
b = a[:]
for i in range(n):
    c = 1
    while b[i] % 2 == 0:
        c *= 2
        b[i] //= 2
    if c > r:
        r = c
for i in range(n):
    if a[i] % r == 0:
        k += 1
print(r, k)









n = int(input())
arr = list(map(int, input().split()))
step = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912]
r = 0
c = 0
for i in range(n):
    for j in range(29, -1, -1):
        if arr[i] % step[j] == 0:
            break
    if j == r:
        c += 1
    if j > r:
        r = j
        c = 1
        
print(step[r], c)

n = int(input())
arr = list(map(int, input().split()))
ans = [0 for i in range(n)]
j = 2
for i in range(n):
    while arr[i] % j == 0:
        ans[i] += 1
        arr[i] //= j
print(2 ** max(ans), ans.count(max(ans)))


def step(x):
	res = 0
	while x > 0 and x % 2 ** (res + 1) == 0:
		res += 1
	return res

n = int(input())
x = list(map(int, input().split()))
r = 0
m = 0
for i in range(n):
	if step(x[i]) > r:
		m = 1
		r = step(x[i])
	elif step(x[i]) == r:
		m += 1
print(2 ** r, m)

n=int(input())
a=list(map(int,input().split()))
r=2
k=0
r1=1
k1=0
t=True
while t:
    for i in range(n):
        if a[i]%r1==0:
            k1+=1
    if k1!=0:
        k=k1
        k1=0
        r=r1
        r1*=2
        t=True
    else:
        break
print(r,k)
    


n = int(input())
a = list(map(int, input().split()))

ans = 1
ansc = 0

for x in a:
   i = 0
   while (x % (2 ** i) == 0):
      i += 1
   i -= 1
   if (2 ** i == ans):
      ansc += 1
   if (2 ** i > ans):
      ans = 2 ** i
      ansc = 1

print(str(ans) + ' ' + str(ansc))

n=int(input())
a=list(map(int,input().split()))
k=1
n=0
for i in range(len(a)):
    s=a[i]
    f=True
    while f:
        if s%(k*2)==0:
            k*=2
        else:
            f=False
    
for i in range(len(a)):
    if a[i]%k==0:
        n+=1
print(k,n)
        
        
    
    


n = int(input())
a = [0]*n
s = input().split()
x = 0
y = 0
b = []
for i in range(n):
    a[i] = int(s[i])
for i in range(n):
    while (a[i])%2==0:
        a[i]=(a[i]//2)
        x += 1
    b.append(x)
    x = 0
print(2**(max(b)), b.count(max(b)))



r = 1
k = 0
n = int(input())
a = list(map(int, input().split()))
for i in a:
    if (i % r == 0):
        k += 1
    while(i % (r * 2) == 0):
        r *= 2
        k = 1
print(r, k)


from math import *
n = int(input())
data = list(map(int, input().split()))
ans = []
for i in range(100):
    help = [2 ** i, 0]
    for j in range(n):
        if data[j] % (2 ** i) == 0:
            help[1] += 1
    ans.append(help)
ans.sort()
index = 0
while ans[index][1]:
    index += 1
index -= 1
print(*ans[index])

input()
numbers = list(map(int, input().split(" ")))


def max2pow(number):
    answer = []
    for y in range(0, 1000):
        if number % pow(2, y) == 0:
            answer.append(y)
    return max(answer)

ans = []
for x in numbers:
    ans.append(max2pow(x))
ans = pow(2, max(ans))
ans1 = 0
for x in numbers:
    if x % ans == 0:
        ans1 += 1
print(ans, ans1)


n = int(input())
a = [int(i) for i in input().split()]
b = 0
c = 0
d = []
for i in range(n) :
    while True :
        b = a[i] / 2 ** c
        if b != int(b) :
            break
        c += 1
    d.append(2 ** (c-1))
    c = 0
p = max(d)
p1 = d.count(p)
print(p , p1)

n = int(input())
s = list(map(int,input().split()))
x = n
d=2
c=0
used = [False]*n
while x>0:
    c=x
    for i in range(n):
        if used[i]==True:
            continue
        if s[i]%d!=0:
            x -= 1
            used[i]=True
    d *= 2
print(d//4,c)

maxst = 0
count = 0
n = int(input())
M = input().split()
for i in range(0,n):
    ni = int(M[i])
    for j in range(maxst,30):
        if ni % 2**j==0:
            if maxst<j:
                maxst = j
                count = 0
            count += 1
        else: break
print(2**maxst,count)


import math

n=int(input())
a=[int(i) for i in input().split()]
def checkStepen(a):
    stepen=0
    while True:
        if a%2==0:
            a//=2
            stepen+=1
        else: break;
    return 2**stepen
r=0
max=0
for i in a:
    k=checkStepen(i)
    if(k>r):
        max=1
        r=k
    elif (k==r):
        max+=1
print(r,max)

n = int(input())
a = list(map(int,input().split()))

k = 1

for i in range(n):
    k *= 2
    while a[i]%k == 0:
        k *= 2
    k //= 2
x = 0
for i in range(n):
    if a[i]%k == 0:
        #print(1,end=' ')
        x += 1
#print()
print(k,x)

a = []
n = int(input())
a += (int(i) for i in input().split())
r, m = 1, 1
while m != 0:
    m2 = m
    m = 0
    for i in range(n):
        if a[i] % r == 0:
            m += 1
    if m != 0:
        r = r * 2
    else:
        break
print(r // 2, m2)

a=int(input())
b=list(map(int, input().split()))
m=max(b)
r=0
f=0
u=0
o=0
k=0
while f<=m:
    f=2**r
    r+=1
r-=1
for i in range(a):
    for j in range(r):
        if b[i]%(2**j)==0:
            if 2**j>o:
                o=2**j
for i in range(a):
    if b[i]%o==0:
        k+=1
print(o,k)