Checkpoint

#!/usr/bin/env python
import sys
from math import sqrt
from multiprocessing import Pool

def time_function(func):
    def wrapped_func(*args, **kwargs):
        from time import time
        start = time()
        sys.stderr.write('Function %s started\n' % (func.__name__,))
        res = func(*args, **kwargs)
        sys.stderr.write('Function %s finished in %.6fs\n' % (func.__name__, time() - start))
        return res
    return wrapped_func

class Problem(object):
    @time_function
    def __init__(self, data):
        self.s = int(data[0])
        self.divs = list(self.get_divisors())

    def get_pascal(self, row = 0):
        result = [1]
        for i in range(1, 1 + row/2):
            result.append((result[i-1]*(row + 1 - i))/i)
        return result


    def lookup_pascal(self, n):
        row = 1
        not_found = True
        if n == 1:
            return 0, 1
        r, c = n, 1
        while not_found:
            row += 1
            res = self.get_pascal(row)
            to_check = res[2:]
            if n in to_check:
                r, c = row, to_check.index(n)
                not_found = False
            if to_check and to_check[0] > n:
                break
        return r - c, c


    def get_divisors(self):
        for i in range(1, 1 + int(sqrt(self.s))):
            if self.s % i == 0:
                yield i, self.s/i

    @time_function
    def get_solution(self, msg = None):
        m = self.s + 1
        for n, p in self.divs:
            r1, c1 = self.lookup_pascal(n)
            r2, c2 = self.lookup_pascal(p)
            if r1 + c1 + r2 + c2 < m:
                m = r1 + c1 + r2 + c2

        return m

@time_function
def main():
    input_file = open('input.txt')
    n = int(input_file.readline().strip())
    results = {}
    pool = Pool()
    for i in range(1, n + 1):
        data = map(int, input_file.readline().strip().split(' '))
        results[i] = pool.apply_async(Problem(data).get_solution)
    pool.close()
    pool.join()

    for i in sorted(results):
        print "Case #%d: %s" % (i, str(results[i].get()))

if __name__ == '__main__':
    from doctest import testmod
    print >> sys.stderr, testmod()
    main()