PBCTF 2020 Crypto Writeups

I participated in PBCTF 2020 as a member of Super Guesser. We reached 2nd place :) 

Huge congratulations and respect to zer0pts, a team that clearly doesn't fit their team name.

I solved : QueenSarah2, Strong Cipher (with reversing help), LeaK, Special Gift, Special Gift Revenge, Find rbtree.

QueenSarah2

from string import ascii_lowercase
from itertools import product
from random import SystemRandom
from math import ceil, log
from secretstuff import FLAG
 
random = SystemRandom()
ALPHABET = ascii_lowercase + "_"
assert all(char in ALPHABET for char in FLAG)
 
bigrams = [''.join(bigram) for bigram in product(ALPHABET, repeat=2)]
random.shuffle(bigrams)
 
S_box = {}
for i in range(len(ALPHABET)):
    for j in range(len(ALPHABET)):
        S_box[ALPHABET[i]+ALPHABET[j]] = bigrams[i*len(ALPHABET) + j]
 
assert len(set(S_box.keys())) == 27*27
 
def encrypt(message):
    if len(message) % 2:
        message += "_"
 
    message = list(message)
    rounds = int(2 * ceil(log(len(message), 2))) # The most secure amount of rounds
 
    for round in range(rounds):
        # Encrypt
        for i in range(0, len(message), 2):
            message[i:i+2] = S_box[''.join(message[i:i+2])]
 
        # Shuffle, but not in the final round
        if round < (rounds-1):
            message = [message[i] for i in range(len(message)) if i%2 == 0] + [message[i] for i in range(len(message)) if i%2 == 1]
 
    return ''.join(message)
 
# 123456 -> 135246
if __name__ == "__main__":
    print("This is a restricted service! Decrypt this password to proceed:")
    print({encrypt(FLAG)})
 
    for _ in range(1500):
        question = input("> ").strip()
        assert 0 < len(question) <= 10000
 
        if not question:
            print("Bye.")
            break
 
        elif question == FLAG:
            print(f"You got it. The flag is pbctf{{{FLAG}}}")
            break
 
        else:
            print("That's not quite right. Your password encrypts to this:")
            print(encrypt(question))
 
 

We have a secret permutation of bigrams, which are used to encrypt the messages. By sending all $27^2$ bigrams, we can easily calculate the square of the permutation. This is because with messages of length 2, we go through 2 rounds of encryption, and the last shuffle algorithm doesn't actually shuffle anything. However, knowing the square of the permutation does not imply we cannot recover the permutation directly. This is only possible in certain cases - such as when all cycles of the squared permutation have different length. This happens with around 2% probability. Therefore, we may try to recover the original permutation with this idea, and recover the flag by reversing the encryption process. I got it with around 20 tries, so I got lucky here a bit. Looking at the flag, it looks like there should be a cooler solution.

def connect():
    r = remote('queensarah2.chal.perfect.blue', 1)
    return r
 
def get_index(t):
    if ord('a') <= ord(t) <= ord('z'):
        return ord(t) - ord('a')
    return 26 
 
def attempt():
    dcyc = [0] * (27 * 27)
    AL = ascii_lowercase + "_"
    r = connect()
    r.recvline()
    true_val = r.recvline()[2:-3].decode()
    for i in range(0, 27):
        for j in range(0, 27):
            s = AL[i] + AL[j]
            print(s)
            r.sendline(s)
            r.recvline()
            res = r.recvline()[0:2].decode()
            idx = 27 * get_index(res[0]) + get_index(res[1])
            dcyc[27 * i + j] = idx # square of permutation
    vis = [0] * (27 * 27 + 5)
    sz = [0] * (27 * 27 + 5)
    fk = [0] * (27 * 27 + 5)
    # get cycles of the square permutation 
    for i in range(0, 27 * 27):
        if vis[i] == 1:
            continue
        cur, t = i, 0
        L = []
        while vis[cur] == 0:
            L.append(cur)
            t += 1
            vis[cur] = 1
            cur = dcyc[cur]
        if sz[t] >= 1 or t % 2 == 0: # all cycle's length different
            return
        sz[t] += 1
        for x in L:
            fk[x] = t
    # compute original permutation
    cyc = [0] * (27 * 27)
    for i in range(0, 27 * 27):
        it = (fk[i] + 1) // 2
        u = i
        for j in range(0, it):
            u = dcyc[u]
        cyc[i] = u
    invcyc = [0] * (27 * 27)
    for i in range(0, 27 * 27):
        invcyc[cyc[i]] = i
    # decryption process
    rounds = int(2 * math.ceil(math.log(len(true_val), 2)))
    for i in range(0, rounds):
        if i != 0:
            msg = ''
            for j in range(0, len(true_val) // 2):
                msg = msg + true_val[j]
                msg = msg + true_val[j + len(true_val) // 2]
            true_val = msg
        msg = ''
        for j in range(0, len(true_val), 2):
            cc = 27 * get_index(true_val[j]) + get_index(true_val[j+1])
            cc = invcyc[cc]
            u = cc // 27
            v = cc % 27
            msg += AL[u]
            msg += AL[v]
        true_val = msg
    print(true_val)
    r.sendline(true_val)
    print(r.recvline())
 
NUM_ATTEMPT = 1000
for i in range(0, NUM_ATTEMPT):
    print("[+] Attempt ", i)
    attempt()

Strong Cipher

After reversing, we found out that the encryption process was a simple vigenere cipher, with $GF(2^8)$ multiplications instead of addition. By brute forcing key length and selecting keys that gave maximum number of readable characters, we can recover the plaintext. I wasted a lot of time by incorrectly assuming that the plaintext is 100% readable. oof

def gf2(src1, src2):
    ret = 0
    for i in range(0, 8):
        if (src2 & (1 << i)) > 0:
            ret = ret ^ (src1 << i)
    for i in range(14, 7, -1):
        p = 0x11B << (i - 8)
        if (ret & (1 << i)) > 0:
            ret = ret ^ p
    assert 0 <= ret < 256
    return ret
 
f = open("ciphertext", "rb")
f = f.read()
 
L = len(f)
print(L)
 
cc = []
for i in range(12, 13): # should brute over 1 ~ 16
    for j in range(0, i):
        cmx, whi = 0, 0
        for k in range(1, 256):
            cnt = 0
            for l in range(j, L, i):
                t = gf2(k, f[l]) 
                if 32 <= t <= 128:
                    cnt += 1
            if cmx < cnt:
                cmx = cnt
                whi = k
        cc.append(whi)
 
res = b""
 
for i in range(0, L):
    res += long_to_bytes(gf2(cc[i % 12], f[i]))
 
print(res)

LeaK

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Private_key
from flag import flag
import hashlib
import random
 
g = SECP256k1.generator
order = int(SECP256k1.order)
secret = random.randrange(2, order - 1)
pubkey = Public_key(g, g * secret)
privkey = Private_key(pubkey, secret)
 
arr = []
for i in range(30):
    h = random.randrange(2, order - 1)
    k = random.randrange(2, order - 1)
    sig = privkey.sign(h, k)
    
    lea_k = int("0x" + "{:064x}".format(k)[10:-10], 16)
 
    arr.append((h, lea_k, int(sig.r), int(sig.s)))
 
print(arr)
 
sha256 = hashlib.sha256()
sha256.update(str(secret).encode())
key = sha256.digest()
 
aes = AES.new(key, mode=AES.MODE_ECB)
print(aes.encrypt(pad(flag, 16)).hex())

It's yet another hidden number problem. We have

$$s \equiv k^{-1}(h + r \cdot pvk) \pmod{n}$$ $$ (2^{216} \cdot small_1 + 2^{40} \cdot leak + small_2)s \equiv h + r \cdot pvk \pmod{n}$$ $$ r \cdot pvk \equiv 2^{216}s \cdot small_1 + s \cdot small_2 + 2^{40}s \cdot leak - h \pmod{n}$$

Now we can work with $r$, $2^{216}s$, $s$ and $n$ to make $2^{40}s \cdot leak - h$. Babai's algorithm can do this.

Small notes on the code below - I have used the following tricks to get the secret key.

• The equation above is an equality, so we have to force it to be equal. 
• This is done by scaling - i.e. multiplying a super large integer $n^2$ to the respective columns.
• We have $pvk$ to be between $0$ and $n$, but $small_1, small_2$ between $0$ and $2^{40}$. 
• We need the two to have a similar order for CVP algorithm to respect the bounds on $small_1, small_2$, so scale it by $n/2^{40}$. 
• We have 30 signatures, but with the matrix below, using all of them takes too long. Using 10 is enough.

def Babai_closest_vector(M, G, target):
        small = target
        for _ in range(1):
            for i in reversed(range(M.nrows())):
                c = ((small * G[i]) / (G[i] * G[i])).round()
                small -=  M[i] * c
        return target - small 
 
NUM = 10
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
SIG = [] ## signature
 
M = Matrix(ZZ, 3 * NUM + 1, 3 * NUM + 1)
for i in range(0, NUM):
    M[0, i] = SIG[i][2] * n * n
M[0, NUM] = 1
 
for i in range(0, NUM):
    M[2 * i + 1, i] = (2 ** 216) * SIG[i][3] * n * n
    M[2 * i + 2, i] = SIG[i][3] * n * n
    M[2 * i + 1, NUM + 2 * i + 1] = n // (2 ** 40)
    M[2 * i + 2, NUM + 2 * i + 2] = n // (2 ** 40)
for i in range(0, NUM):
    M[2 * NUM + 1 + i, i] = n * n * n
Target = [0] * (3 * NUM + 1)
for i in range(0, NUM):
    Target[i] = ((SIG[i][1] * (2 ** 40) * SIG[i][3] - SIG[i][0]) % n) * n * n
Target = vector(Target)
M = M.LLL()
GG = M.gram_schmidt()[0]
TT = Babai_closest_vector(M, GG, Target)
print(TT - Target)
print(TT[NUM] % n) ## secret

Special Gift

from Crypto.Util.number import getStrongPrime, inverse, bytes_to_long, GCD as gcd
from Crypto.Random.random import randint
from flag import flag
 
p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
 
# Hehe, boi
while True:
    d = randint(int(N ** 0.399), int(N ** 0.4))
    if gcd(d, phi) == 1:
        break
 
e = inverse(d, phi)
 
# Here's a special gift. Big.
gift = d >> 120
 
enc = pow(bytes_to_long(flag), e, N)
 
print("N =", N)
print("e =", e)
print("gift =", gift)
print("enc =", enc)

My best achievement in this CTF is first solving this with unintended sol, forcing rbtree to write a revenge challenge.

This problem is also the reason I'm writing stuff up for this CTF in 2am ^__^

My solution resembles my alternate solution for crypto01 from SECCONCTF a little bit.

We start with $$ ed = k\phi(n) + 1 = k(n-p-q+1)+1 = kn - k(p+q-1) + 1$$

Since $e \approx n$ and $d \approx n^{0.4}$, we have $k \approx n^{0.4}$ as well. Also, we know that $$ 2\sqrt{n} \le p+q \le 3\sqrt{n/2}$$ so combining, we have something like $0 \le k(p+q-1) - 1 \le 3 \cdot n^{0.9}$. I calculated constants like $3$ very loosely, btw. 

Therefore, we have an interval of length $3 \cdot n^{0.9}$ that $ed \pmod{n}$ must lie inside. 

Writing $d = gift \cdot 2^{120} + c$ with $0 \le c < 2^{120}$, we have an interval on $ec \pmod{n}$. 

We have $2^{120}$ candidates for $c$, and we have a condition on $ec \pmod{n}$ that has, heuristically, a probability of $3 \cdot n^{-0.1}$ of satisfying. Therefore, we can expect around $2^{120} \cdot 3 \cdot n^{-0.1} \approx 3 \cdot 2^{18}$ "true" candidates for $c$. This is not an unreasonably large number, so if we can find those true candidates quickly, we can brute force every one of them to find the flag. 

How do we find the true candidates for $c$? This is equivalent to finding the smallest positive integer $x$ such that $$L \le Ax \pmod{M} \le R$$ for given $A, M, L, R$ quickly. Polynomial time solution of this problem was mentioned in the crypto01 problem writeup linked above. 

It takes around 30 minutes to compute the flag, and it iterates over around 700,000 candidates as expected.

The flag prints the link to a paper that contains the intended solution.

def ceil(n, m):
    return (n + m - 1) // m
 
def optf(A, M, L, R):
    if L == 0:
        return 0
    if 2 * A > M:
        L, R = R, L
        A = M - A
        L = M - L
        R = M - R
    cc_1 = ceil(L, A)
    if A * cc_1 <= R:
        return cc_1
    cc_2 = optf(A - M % A, A, L % A, R % A)
    return ceil(L + M * cc_2, A)
 
N = 124588792854585991543122421017579759242707321792822503200983206042530513248160179498235727796077646122690756838184806567078369714502863053151565317001149999657802192888347495811627518984421857644550440227092744651891241056244522365071057538408743656419815042273198915328775318113249292516318084091006804073157
e = 109882604549059925698337132134274221192629463500162142191698591870337535769029028534472608748886487359428031919436640522967282998054300836913823872240009473529848093066417214204419524969532809574214972094458725753812433268395365056339836734440559680393774144424319015013231971239186514285386946953708656025167
gift = 870326170979229749948990285479428244545993216619118847039141213397137332130507928675398
enc = 67594553703442235599059635874603827578172490479401786646993398183588852399713973330711427103837471337354320292107030571309136139408387709045820388737058807570181494946004078391176620443144203444539824749021559446977491340748598503240780118417968040337516983519810680009697701876451548797213677765172108334420
 
CR = (-e * (gift << 120)) % N
CL = (-e * (gift << 120) - 3 * (int)(N ** 0.9)) % N
 
lst = 0
 
while lst <= (2 ** 120):
    # find next solution by shifting
    NL = (CL - e * (lst + 1)) % N
    NR = (CR - e * (lst + 1)) % N
    if NL > NR:
        # 0 is a solution
        lst = lst + 1
    else:
        # find actual solution
        cc = optf(e, N, NL, NR)
        lst = lst + 1 + cc
    real_d = gift * (1 << 120) + lst
    s = long_to_bytes(pow(enc, real_d, N))
    if b"pbctf" in s:
        print(s)

Special Gift Revenge

from Crypto.Util.number import getStrongPrime, inverse, bytes_to_long, GCD as gcd
from Crypto.Random.random import randint
from flag import flag
import gmpy2
 
p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
 
# Hehe, boi
while True:
    d = randint(int(N ** gmpy2.mpfr(0.599)), int(N ** gmpy2.mpfr(0.6)))
    if gcd(d, phi) == 1:
        break
 
e = inverse(d, phi)
 
# Here's a special gift. Big.
gift = d >> 120
 
enc = pow(bytes_to_long(flag), e, N)
 
print("N =", N)
print("e =", e)
print("gift =", gift)
print("enc =", enc)

Now this problem blocks the unintended sol above. Therefore, we should implement the paper in the previous flag.

The implementation is not tough, but I surely learned a lot of lattice stuff from it. Thanks to rbtree :)

The flag is pbctf{thank_you_rkm0959,_for_finding_unintended_solution} which is pretty cool :P

## modified https://github.com/ubuntor/coppersmith-algorithm/blob/main/coppersmith.sage
 
debug = True
 
N = 123463519828344660835965296108959625188149729700517379543746606603601816029557213728343115758280318474617032830851553509268562367217512005079977122560679743955588214135519642513042848616372204042776892196887455692479457740367547908255044784496969010537283159300508751036032559594474145098337531029291955103059
e = 85803665824396212221464259773478155183477895540333642019501498374139506738444521180470104195883386495607712971252463223185914391456070458788554837326327618859712794129800329295751565279950274474800740076285111503780662397876663144946831503522281710586712396810593754749589799811545251575782431569881989690861
gift = 46710143823773072238724337855139753113453277386728402328859555407710009799097841900723288768522450009531777773692804519189753306306645410280934372812
enc = 106121451638162677594573310940827829041097305506084523508481527070289767121202640647932427882853090304492662258820333412210185673459181060321182621778215705296467924514370932937109363645133019461501960295399876223216991409548390823510949085131028770701612550221001043472702499511394058569487248345808385915190
 
delta = 0.6
gamma = 120 / 1022
lam = max(gamma, delta - 0.5)
d_0 = (gift << 120) + (1 << 119) 
k_0 = (e * d_0 - 1) // N
X = (int)(4 * (N ** lam))
Y = (int)(3 * ((N/2) ** 0.5))
m = 5
t = 3
 
P.<x,y> = PolynomialRing(ZZ)
pol = (1 + k_0 * N) % e + (k_0 % e) * y + (N % e) * x + x * y
 
while gcd(pol(0,0), X) != 1:
    X = next_prime(X, proof=False)
 
while gcd(pol(0,0), Y) != 1:
    Y = next_prime(Y, proof=False)
 
polynomials = []
for j in range(0, m+1):
    for i in range(0, m-j+t+1):
        polynomials.append(x^i * pol^j * e^(m-j))
for j in range(0, m+1):
    for i in range(1, m-j+1):
        polynomials.append(y^i * pol^j * e^(m-j))
 
monomials = []
for i in polynomials:
    for j in i.monomials():
        if j not in monomials:
            monomials.append(j)
monomials.sort()
 
L = matrix(ZZ,len(monomials))
for i in range(len(monomials)):
    for j in range(len(monomials)):
        L[i,j] = polynomials[i](X*x,Y*y).monomial_coefficient(monomials[j])
 
L = matrix(ZZ,sorted(L,reverse=True))
L = L.LLL()
roots = []
 
for i in range(L.nrows()):
    for j in range(i+1, L.nrows()):
        pol1 = P(sum(map(mul, zip(L[i],monomials)))(x/X,y/Y))
        pol2 = P(sum(map(mul, zip(L[j],monomials)))(x/X,y/Y))
        r = pol1.resultant(pol2, y)
        if r.is_constant():
            continue
        for x0, _ in r.univariate_polynomial().roots():
            if x0 in [i[0] for i in roots]:
                continue
            if debug:
                print("Potential x0:",x0)
            for y0, _ in pol1(x0,y).univariate_polynomial().roots():
                if debug:
                    print("Potential y0:",y0)
                if (x0,y0) not in roots:
                    roots.append((x0,y0))
print(roots)
 

Find rbtree

prop = {
    "Eyewear": ["Glasses", "Monocle", "None"],
    "Eye color": ["Brown", "Blue", "Hazel"],
    "Hair": ["Straight", "Curly", "Bald"],
    "Outerwear": ["Coat", "Hoodie", "Poncho"],
    "T-shirt color": ["Red", "Orange", "Green"],
    "Trousers": ["Jeans", "Leggings", "Sweatpants"],
    "Socks color": ["Black", "Gray", "White"],
    "Shoes": ["Boots", "Slippers", "Sneakers"],
}
 
 
def stage(num_stage, num_people, num_ask):
    print("STAGE {} / 30".format(num_stage))
    print("Generating people... (and rbtree)")
 
    people = list(itertools.product(*prop.values()))
    random.shuffle(people)
    people = people[:num_people]
    rbtree = random.choice(people)
 
    print("=" * 29)
    for idx, person in enumerate(people):
        print(" ".join(" [PERSON {:4d}] ".format(idx + 1)))
        for prop_name, prop_val in zip(prop.keys(), person):
            print("{:14s}: {}".format(prop_name, prop_val))
        print("=" * 29)
 
    print("Now ask me!")
 
    for i in range(num_ask):
        prop_name = input("? > ")
        if prop_name == 'Solution':
            break
        if prop_name not in prop:
            return False
        
        prop_ask = input("! > ").strip().split(' ')
        for val in prop_ask:
            if val not in prop[prop_name]:
                return False
 
        if set(rbtree) & set(prop_ask):
            print("YES")
        else:
            print("NO")
 
    rbtree_guess = tuple(input("rbtree > ").strip().split(' '))
 
    if rbtree == rbtree_guess:
        return True
    else:
        return False
 
 
def main():
 
    cases = [(5, 3), (7, 3), (10, 4), (15, 4), (20, 5), (25, 5), (50, 6), (75, 7), (100, 8), (250, 9)]
    cases += [(400, 10)] * 5 + [(750, 11)] * 5 + [(1000, 12)] * 5 + [(1600, 12)] * 5
 
    for idx, (num_people, num_ask) in enumerate(cases):
        if not stage(idx + 1, num_people, num_ask):
            print("WRONG :(")
            return
        print("You found rbtree!")
              
    with open("flag.txt", "r") as f:
        print(f.read())
 
 
if __name__ == "__main__":
    try:
        main()
    finally:
        print("BYEBYE!")
        exit(0)

I tried the most naive way - finding the question that has "the best worst case". If I had used all my queries and I still had multiple candidates left, I chose one randomly and reported it as the answer. It looked it had decent chances of succeeding, so my teammates ran multiple instances :) I was worried about the server being adaptive like some challenges in competitive programming, but we got the flag.

UPD: So more of a backstory - I had realized that the number of candidates never decreased by more than half. This is strange unless the server is set up against you. This was the main fact that caused me to become worried about adversarial server. Turns out the server *was* adversarial, but wasn't perfectly so. The solution below is clearly unintended (smarter solutions should exist) but the server's antics can't really stop it from getting the flag. I guess they didn't block choosing one random answer while there are multiple candidates. 

prop_list = ["Eyewear", "Eye color", "Hair", "Outerwear", "T-shirt color", "Trousers", "Socks color", "Shoes"]
prop = {
    "Eyewear": ["Glasses", "Monocle", "None"],
    "Eye color": ["Brown", "Blue", "Hazel"],
    "Hair": ["Straight", "Curly", "Bald"],
    "Outerwear": ["Coat", "Hoodie", "Poncho"],
    "T-shirt color": ["Red", "Orange", "Green"],
    "Trousers": ["Jeans", "Leggings", "Sweatpants"],
    "Socks color": ["Black", "Gray", "White"],
    "Shoes": ["Boots", "Slippers", "Sneakers"],
}
 
def checker(i, j, desc):
    for t in range(0, 3):
        if (1 << t) & j and desc[i] == prop[prop_list[i]][t]:
            return True
    return False
 
def ask_query(whi_i, whi_j):
    r.sendline(prop_list[whi_i])
    s = ""
    for i in range(0, 3):
        if whi_j & (1 << i):
            s += prop[prop_list[whi_i]][i]
            s += " "
    s = s[:-1]
    r.sendline(s)
    res = r.recvline()
    print(res)
    sx = False
    if b"YES" in res:
        sx = True
    return sx
 
def gogo(ppl_desc, num_query):
    print(len(ppl_desc))
    if len(ppl_desc) == 1:
        if num_query >= 1:
            r.sendline(b"Solution")
        s = ""
        for i in range(0, 8):
            s += ppl_desc[0][i]
            if i != 7:
                s += " "
        r.sendline(s)
        r.recvline()
        return
    if num_query == 0:
        t = random.randrange(0, len(ppl_desc))
        s = ""
        for i in range(0, 8):
            s += ppl_desc[t][i]
            if i != 7:
                s += " "
        r.sendline(s)
        r.recvline()
        return
    T = len(ppl_desc)
    whi_i, whi_j, opt = -1, -1, 0
    for i in range(0, 8):
        for j in range(1, 4):
            cnt = 0
            for k in range(0, T):
                ex = checker(i, j, ppl_desc[k])
                if ex == True:
                    cnt += 1
            if min(cnt, T-cnt) > opt:
                opt = min(cnt, T-cnt)
                whi_i, whi_j = i, j
    sx = ask_query(whi_i, whi_j)
    nppl_desc = []
    for k in range(0, T):
        ex = checker(whi_i, whi_j, ppl_desc[k])
        if ex == sx:
            nppl_desc.append(ppl_desc[k])
    gogo(nppl_desc, num_query - 1)
    return
 
def solve(num_pp, num_ask):
    print(r.recvline())
    print(r.recvline())
    print(r.recvline())
    ppl_desc = []
    for i in range(0, num_pp):
        cur = []
        r.recvline()
        for j in range(0, 8):
            s = r.recvline()
            s = s.split(b":")[1]
            s = s[1:-1].decode()
            cur.append(s)
        ppl_desc.append(cur)
        r.recvline()
    r.recvline()
    gogo(ppl_desc, num_ask)
 
 
r = remote("find-rbtree.chal.perfect.blue", 1)
 
for i in range(0, 9):
    r.recvline()
 
cases = [(5, 3), (7, 3), (10, 4), (15, 4), (20, 5), (25, 5), (50, 6), (75, 7), (100, 8), (250, 9)]
cases += [(400, 10)] * 5 + [(750, 11)] * 5 + [(1000, 12)] * 5 + [(1600, 12)] * 5
 
for i in range(0, 30):
    solve(cases[i][0], cases[i][1])
 
print(r.recvline())