import itertools

def is_int(x):
    eps = 1e-4
    if abs(x - int(x)) < eps:
        return 1
    return 0


def gcd(a, b):
    while b != 0:
       t = b
       b = a % t
       a = t
    return a


def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]


def get_primes(max_val):
    vals = list(range(0,max_val+1))
    vals[1] = 0;

    for i in range(2,len(vals)/2 + 2):
      v = vals[i]
      # if v != 0 , then v is prime
      if v == 0:
          continue
      m = 2
      r = m*v

      while r <= max_val:
          vals[r] = 0
          m += 1
          r = m*v
    X = []
    for v in vals:
        if v != 0:
            X.append(v)
    return X

def digits_to_num(digits):
    val = 0 
    j = 0
    for i in range(len(digits)-1,-1,-1):
        val += (10**i)*digits[j]
        j += 1
    return val

def get_digits(num):
    digit_count = 0;
    if num < 10:
        digit_count = 1
    elif num < 100:
        digit_count = 2
    elif num < 1000:
        digit_count = 3
    elif num < 10000:
        digit_count = 4
    elif num < 100000:
        digit_count = 5
    elif num < 1000000:
        digit_count = 6
    elif num < 10000000:
        digit_count = 7
    elif num < 100000000:
        digit_count = 8
    elif num < 1000000000:
        digit_count = 9
    else:
        rem = 1
        digit_count = 10
        val = (10**digit_count)
        rem = num/val
        while rem != 0:
            digit_count += 1
            val = (10**digit_count)
            rem = num/val
        

    digits = []
    t = num
    for i in range(digit_count-1,-1,-1):
        p = 10**i
        r = t/p
        digits.append(int(r))
        t = t - r*p
    return digits


def prime_factors(n):
    "Returns all the prime factors of a positive integer"
    factors = []
    d = 2
    while (n > 1):
        while (n%d==0):
            factors.append(d)
            n /= d
        d = d + 1
        if (d*d>n):
            if (n>1): factors.append(n);
            break;
    return factors



def factorGenerator(val):
  pfactors = prime_factors(val)
  pfactors.sort()
  factor_list = []
  for key,group in itertools.groupby(pfactors):
      factor_list.append( (key,len(list(group)) ) )

  return factor_list

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

d152b4090dd164355ec7701c13acd75997695bb5
<mask token>


def is_int(x):
    eps = 0.0001
    if abs(x - int(x)) < eps:
        return 1
    return 0


def gcd(a, b):
    while b != 0:
        t = b
        b = a % t
        a = t
    return a


def all_perms(elements):
    if len(elements) <= 1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]


def get_primes(max_val):
    vals = list(range(0, max_val + 1))
    vals[1] = 0
    for i in range(2, len(vals) / 2 + 2):
        v = vals[i]
        if v == 0:
            continue
        m = 2
        r = m * v
        while r <= max_val:
            vals[r] = 0
            m += 1
            r = m * v
    X = []
    for v in vals:
        if v != 0:
            X.append(v)
    return X


def digits_to_num(digits):
    val = 0
    j = 0
    for i in range(len(digits) - 1, -1, -1):
        val += 10 ** i * digits[j]
        j += 1
    return val


<mask token>


def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
    return factors


def factorGenerator(val):
    pfactors = prime_factors(val)
    pfactors.sort()
    factor_list = []
    for key, group in itertools.groupby(pfactors):
        factor_list.append((key, len(list(group))))
    return factor_list


<mask token>

<mask token>


def is_int(x):
    eps = 0.0001
    if abs(x - int(x)) < eps:
        return 1
    return 0


def gcd(a, b):
    while b != 0:
        t = b
        b = a % t
        a = t
    return a


def all_perms(elements):
    if len(elements) <= 1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]


def get_primes(max_val):
    vals = list(range(0, max_val + 1))
    vals[1] = 0
    for i in range(2, len(vals) / 2 + 2):
        v = vals[i]
        if v == 0:
            continue
        m = 2
        r = m * v
        while r <= max_val:
            vals[r] = 0
            m += 1
            r = m * v
    X = []
    for v in vals:
        if v != 0:
            X.append(v)
    return X


def digits_to_num(digits):
    val = 0
    j = 0
    for i in range(len(digits) - 1, -1, -1):
        val += 10 ** i * digits[j]
        j += 1
    return val


def get_digits(num):
    digit_count = 0
    if num < 10:
        digit_count = 1
    elif num < 100:
        digit_count = 2
    elif num < 1000:
        digit_count = 3
    elif num < 10000:
        digit_count = 4
    elif num < 100000:
        digit_count = 5
    elif num < 1000000:
        digit_count = 6
    elif num < 10000000:
        digit_count = 7
    elif num < 100000000:
        digit_count = 8
    elif num < 1000000000:
        digit_count = 9
    else:
        rem = 1
        digit_count = 10
        val = 10 ** digit_count
        rem = num / val
        while rem != 0:
            digit_count += 1
            val = 10 ** digit_count
            rem = num / val
    digits = []
    t = num
    for i in range(digit_count - 1, -1, -1):
        p = 10 ** i
        r = t / p
        digits.append(int(r))
        t = t - r * p
    return digits


def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
    return factors


def factorGenerator(val):
    pfactors = prime_factors(val)
    pfactors.sort()
    factor_list = []
    for key, group in itertools.groupby(pfactors):
        factor_list.append((key, len(list(group))))
    return factor_list


<mask token>

<mask token>


def is_int(x):
    eps = 0.0001
    if abs(x - int(x)) < eps:
        return 1
    return 0


def gcd(a, b):
    while b != 0:
        t = b
        b = a % t
        a = t
    return a


def all_perms(elements):
    if len(elements) <= 1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]


def get_primes(max_val):
    vals = list(range(0, max_val + 1))
    vals[1] = 0
    for i in range(2, len(vals) / 2 + 2):
        v = vals[i]
        if v == 0:
            continue
        m = 2
        r = m * v
        while r <= max_val:
            vals[r] = 0
            m += 1
            r = m * v
    X = []
    for v in vals:
        if v != 0:
            X.append(v)
    return X


def digits_to_num(digits):
    val = 0
    j = 0
    for i in range(len(digits) - 1, -1, -1):
        val += 10 ** i * digits[j]
        j += 1
    return val


def get_digits(num):
    digit_count = 0
    if num < 10:
        digit_count = 1
    elif num < 100:
        digit_count = 2
    elif num < 1000:
        digit_count = 3
    elif num < 10000:
        digit_count = 4
    elif num < 100000:
        digit_count = 5
    elif num < 1000000:
        digit_count = 6
    elif num < 10000000:
        digit_count = 7
    elif num < 100000000:
        digit_count = 8
    elif num < 1000000000:
        digit_count = 9
    else:
        rem = 1
        digit_count = 10
        val = 10 ** digit_count
        rem = num / val
        while rem != 0:
            digit_count += 1
            val = 10 ** digit_count
            rem = num / val
    digits = []
    t = num
    for i in range(digit_count - 1, -1, -1):
        p = 10 ** i
        r = t / p
        digits.append(int(r))
        t = t - r * p
    return digits


def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
    return factors


def factorGenerator(val):
    pfactors = prime_factors(val)
    pfactors.sort()
    factor_list = []
    for key, group in itertools.groupby(pfactors):
        factor_list.append((key, len(list(group))))
    return factor_list


def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x * y, [(factors[x][0] ** f[x]) for x in
            range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

import itertools


def is_int(x):
    eps = 0.0001
    if abs(x - int(x)) < eps:
        return 1
    return 0


def gcd(a, b):
    while b != 0:
        t = b
        b = a % t
        a = t
    return a


def all_perms(elements):
    if len(elements) <= 1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]


def get_primes(max_val):
    vals = list(range(0, max_val + 1))
    vals[1] = 0
    for i in range(2, len(vals) / 2 + 2):
        v = vals[i]
        if v == 0:
            continue
        m = 2
        r = m * v
        while r <= max_val:
            vals[r] = 0
            m += 1
            r = m * v
    X = []
    for v in vals:
        if v != 0:
            X.append(v)
    return X


def digits_to_num(digits):
    val = 0
    j = 0
    for i in range(len(digits) - 1, -1, -1):
        val += 10 ** i * digits[j]
        j += 1
    return val


def get_digits(num):
    digit_count = 0
    if num < 10:
        digit_count = 1
    elif num < 100:
        digit_count = 2
    elif num < 1000:
        digit_count = 3
    elif num < 10000:
        digit_count = 4
    elif num < 100000:
        digit_count = 5
    elif num < 1000000:
        digit_count = 6
    elif num < 10000000:
        digit_count = 7
    elif num < 100000000:
        digit_count = 8
    elif num < 1000000000:
        digit_count = 9
    else:
        rem = 1
        digit_count = 10
        val = 10 ** digit_count
        rem = num / val
        while rem != 0:
            digit_count += 1
            val = 10 ** digit_count
            rem = num / val
    digits = []
    t = num
    for i in range(digit_count - 1, -1, -1):
        p = 10 ** i
        r = t / p
        digits.append(int(r))
        t = t - r * p
    return digits


def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
    return factors


def factorGenerator(val):
    pfactors = prime_factors(val)
    pfactors.sort()
    factor_list = []
    for key, group in itertools.groupby(pfactors):
        factor_list.append((key, len(list(group))))
    return factor_list


def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x * y, [(factors[x][0] ** f[x]) for x in
            range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

import itertools

def is_int(x):
    eps = 1e-4
    if abs(x - int(x)) < eps:
        return 1
    return 0


def gcd(a, b):
    while b != 0:
       t = b
       b = a % t
       a = t
    return a


def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]


def get_primes(max_val):
    vals = list(range(0,max_val+1))
    vals[1] = 0;

    for i in range(2,len(vals)/2 + 2):
      v = vals[i]
      # if v != 0 , then v is prime
      if v == 0:
          continue
      m = 2
      r = m*v

      while r <= max_val:
          vals[r] = 0
          m += 1
          r = m*v
    X = []
    for v in vals:
        if v != 0:
            X.append(v)
    return X

def digits_to_num(digits):
    val = 0 
    j = 0
    for i in range(len(digits)-1,-1,-1):
        val += (10**i)*digits[j]
        j += 1
    return val

def get_digits(num):
    digit_count = 0;
    if num < 10:
        digit_count = 1
    elif num < 100:
        digit_count = 2
    elif num < 1000:
        digit_count = 3
    elif num < 10000:
        digit_count = 4
    elif num < 100000:
        digit_count = 5
    elif num < 1000000:
        digit_count = 6
    elif num < 10000000:
        digit_count = 7
    elif num < 100000000:
        digit_count = 8
    elif num < 1000000000:
        digit_count = 9
    else:
        rem = 1
        digit_count = 10
        val = (10**digit_count)
        rem = num/val
        while rem != 0:
            digit_count += 1
            val = (10**digit_count)
            rem = num/val
        

    digits = []
    t = num
    for i in range(digit_count-1,-1,-1):
        p = 10**i
        r = t/p
        digits.append(int(r))
        t = t - r*p
    return digits


def prime_factors(n):
    "Returns all the prime factors of a positive integer"
    factors = []
    d = 2
    while (n > 1):
        while (n%d==0):
            factors.append(d)
            n /= d
        d = d + 1
        if (d*d>n):
            if (n>1): factors.append(n);
            break;
    return factors



def factorGenerator(val):
  pfactors = prime_factors(val)
  pfactors.sort()
  factor_list = []
  for key,group in itertools.groupby(pfactors):
      factor_list.append( (key,len(list(group)) ) )

  return factor_list

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return
