Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на большую степень числа 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: MEDIUM

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)))


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:
		x += 1
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)