{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"challenge_problem_statement\"\u003e\u003cdiv class\u003d\"msB challenge_problem_statement_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cp\u003eSteve loves playing with palindromes. He has a string, \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-1-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, consisting of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-2-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.395ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 600.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e lowercase English alphabetic characters (i.e., \u003ccode\u003ea\u003c/code\u003e through \u003ccode\u003ez\u003c/code\u003e). He wants to calculate the number of ways to insert exactly \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-3-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e lowercase character into string \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-4-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e such that the length of the \u003ca href\u003d\"http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/\"\u003elongest palindromic subsequence\u003c/a\u003e of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-5-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e increases by \u003cem\u003eat least\u003c/em\u003e \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-6-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.211ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 521.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e. Two ways are considered to be \u003cem\u003edifferent\u003c/em\u003e if either of the following conditions are satisfied:\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003eThe positions of insertion are different.\u003c/li\u003e\n\u003cli\u003eThe inserted characters are different. \u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003eThis means there are \u003cem\u003eat most\u003c/em\u003e \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-7-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"12.372ex\" height\u003d\"2.843ex\" style\u003d\"vertical-align: -0.838ex;\" viewBox\u003d\"0 -863.1 5326.9 1223.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M42 313Q42 476 123 571T303 666Q372 666 402 630T432 550Q432 525 418 510T379 495Q356 495 341 509T326 548Q326 592 373 601Q351 623 311 626Q240 626 194 566Q147 500 147 364L148 360Q153 366 156 373Q197 433 263 433H267Q313 433 348 414Q372 400 396 374T435 317Q456 268 456 210V192Q456 169 451 149Q440 90 387 34T253 -22Q225 -22 199 -14T143 16T92 75T56 172T42 313ZM257 397Q227 397 205 380T171 335T154 278T148 216Q148 133 160 97T198 39Q222 21 251 21Q302 21 329 59Q342 77 347 104T352 209Q352 289 347 316T329 361Q302 397 257 397Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(1223,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M630 29Q630 9 609 9Q604 9 587 25T493 118L389 222L284 117Q178 13 175 11Q171 9 168 9Q160 9 154 15T147 29Q147 36 161 51T255 146L359 250L255 354Q174 435 161 449T147 471Q147 480 153 485T168 490Q173 490 175 489Q178 487 284 383L389 278L493 382Q570 459 587 475T609 491Q630 491 630 471Q630 464 620 453T522 355L418 250L522 145Q606 61 618 48T630 29Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2223,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2613,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(3436,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(4436,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(4937,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e different ways to insert exactly \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-8-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e character into a string of length \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-9-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.395ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 600.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e.\u003c/p\u003e\n\n\u003cp\u003eGiven \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-10-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.07ex\" height\u003d\"2.009ex\" style\u003d\"vertical-align: -0.671ex;\" viewBox\u003d\"0 -576.1 460.5 865.1\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e queries consisting of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-11-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.395ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 600.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-12-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.211ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 521.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, and \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-13-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, print the number of different ways of inserting exactly \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-14-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e new lowercase letter into string \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-15-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e such that the length of the longest palindromic subsequence of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-16-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e increases by \u003cem\u003eat least\u003c/em\u003e \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-17-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.211ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 521.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e.\u003c/p\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"challenge_input_format\"\u003e\u003cdiv class\u003d\"msB challenge_input_format_title\"\u003e\u003cp\u003e\u003cstrong\u003eInput Format\u003c/strong\u003e\u003c/p\u003e\u003c/div\u003e\u003cdiv class\u003d\"msB challenge_input_format_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cp\u003eThe first line contains a single integer, \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-1-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.07ex\" height\u003d\"2.009ex\" style\u003d\"vertical-align: -0.671ex;\" viewBox\u003d\"0 -576.1 460.5 865.1\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, denoting the number of queries. The \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-2-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"2.232ex\" height\u003d\"2.509ex\" style\u003d\"vertical-align: -0.671ex;\" viewBox\u003d\"0 -791.3 961 1080.4\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(500,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e subsequent lines describe each query over two lines:\u003c/p\u003e\n\n\u003col\u003e\n\u003cli\u003eThe first line of a query contains two space-separated integers denoting the respective values of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-3-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.395ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 600.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e and \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-4-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.211ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 521.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e. \u003c/li\u003e\n\u003cli\u003eThe second line contains a single string denoting \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-5-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e.\u003c/li\u003e\n\u003c/ol\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"challenge_constraints\"\u003e\u003cdiv class\u003d\"msB challenge_constraints_title\"\u003e\u003cp\u003e\u003cstrong\u003eConstraints\u003c/strong\u003e\u003c/p\u003e\u003c/div\u003e\u003cdiv class\u003d\"msB challenge_constraints_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cul\u003e\n\u003cli\u003e\u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-1-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"10.754ex\" height\u003d\"2.509ex\" style\u003d\"vertical-align: -0.671ex;\" viewBox\u003d\"0 -791.3 4630.1 1080.4\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(778,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1834,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2572,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(3629,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e\u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-2-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"13.404ex\" height\u003d\"2.343ex\" style\u003d\"vertical-align: -0.505ex;\" viewBox\u003d\"0 -791.3 5771.1 1008.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(778,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1834,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2712,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(3769,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M127 463Q100 463 85 480T69 524Q69 579 117 622T233 665Q268 665 277 664Q351 652 390 611T430 522Q430 470 396 421T302 350L299 348Q299 347 308 345T337 336T375 315Q457 262 457 175Q457 96 395 37T238 -22Q158 -22 100 21T42 130Q42 158 60 175T105 193Q133 193 151 175T169 130Q169 119 166 110T159 94T148 82T136 74T126 70T118 67L114 66Q165 21 238 21Q293 21 321 74Q338 107 338 175V195Q338 290 274 322Q259 328 213 329L171 330L168 332Q166 335 166 348Q166 366 174 366Q202 366 232 371Q266 376 294 413T322 525V533Q322 590 287 612Q265 626 240 626Q208 626 181 615T143 592T132 580H135Q138 579 143 578T153 573T165 566T175 555T183 540T186 520Q186 498 172 481T127 463Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(1001,0)\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(1501,0)\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e\u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-3-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"10.896ex\" height\u003d\"2.343ex\" style\u003d\"vertical-align: -0.505ex;\" viewBox\u003d\"0 -791.3 4691.1 1008.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(778,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1834,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2633,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(3690,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M164 157Q164 133 148 117T109 101H102Q148 22 224 22Q294 22 326 82Q345 115 345 210Q345 313 318 349Q292 382 260 382H254Q176 382 136 314Q132 307 129 306T114 304Q97 304 95 310Q93 314 93 485V614Q93 664 98 664Q100 666 102 666Q103 666 123 658T178 642T253 634Q324 634 389 662Q397 666 402 666Q410 666 410 648V635Q328 538 205 538Q174 538 149 544L139 546V374Q158 388 169 396T205 412T256 420Q337 420 393 355T449 201Q449 109 385 44T229 -22Q148 -22 99 32T50 154Q50 178 61 192T84 210T107 214Q132 214 148 197T164 157Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003eIt is guaranteed that \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-4-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e consists of lowercase English alphabetic letters (i.e., \u003ccode\u003ea\u003c/code\u003e to \u003ccode\u003ez\u003c/code\u003e) only.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\u003cstrong\u003eSubtasks\u003c/strong\u003e\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e\u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-5-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"12.241ex\" height\u003d\"2.343ex\" style\u003d\"vertical-align: -0.505ex;\" viewBox\u003d\"0 -791.3 5270.6 1008.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(778,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1834,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2712,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(3769,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(1001,0)\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e for \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-6-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"4.261ex\" height\u003d\"2.343ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -863.1 1834.5 1008.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M164 157Q164 133 148 117T109 101H102Q148 22 224 22Q294 22 326 82Q345 115 345 210Q345 313 318 349Q292 382 260 382H254Q176 382 136 314Q132 307 129 306T114 304Q97 304 95 310Q93 314 93 485V614Q93 664 98 664Q100 666 102 666Q103 666 123 658T178 642T253 634Q324 634 389 662Q397 666 402 666Q410 666 410 648V635Q328 538 205 538Q174 538 149 544L139 546V374Q158 388 169 396T205 412T256 420Q337 420 393 355T449 201Q449 109 385 44T229 -22Q148 -22 99 32T50 154Q50 178 61 192T84 210T107 214Q132 214 148 197T164 157Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M465 605Q428 605 394 614T340 632T319 641Q332 608 332 548Q332 458 293 403T202 347Q145 347 101 402T56 548Q56 637 101 693T202 750Q241 750 272 719Q359 642 464 642Q580 642 650 732Q662 748 668 749Q670 750 673 750Q682 750 688 743T693 726Q178 -47 170 -52Q166 -56 160 -56Q147 -56 142 -45Q137 -36 142 -27Q143 -24 363 304Q469 462 525 546T581 630Q528 605 465 605ZM207 385Q235 385 263 427T292 548Q292 617 267 664T200 712Q193 712 186 709T167 698T147 668T134 615Q132 595 132 548V527Q132 436 165 403Q183 385 203 385H207ZM500 146Q500 234 544 290T647 347Q699 347 737 292T776 146T737 0T646 -56Q590 -56 545 0T500 146ZM651 -18Q679 -18 707 24T736 146Q736 215 711 262T644 309Q637 309 630 306T611 295T591 265T578 212Q577 200 577 146V124Q577 -18 647 -18H651Z\" transform\u003d\"translate(1001,0)\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e of the maximum score.\u003c/li\u003e\n\u003cli\u003e\u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-7-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"13.404ex\" height\u003d\"2.343ex\" style\u003d\"vertical-align: -0.505ex;\" viewBox\u003d\"0 -791.3 5771.1 1008.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(778,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1834,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2712,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(3769,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(1001,0)\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(1501,0)\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e for \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-8-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"4.261ex\" height\u003d\"2.343ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -863.1 1834.5 1008.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M55 458Q56 460 72 567L88 674Q88 676 108 676H128V672Q128 662 143 655T195 646T364 644H485V605L417 512Q408 500 387 472T360 435T339 403T319 367T305 330T292 284T284 230T278 162T275 80Q275 66 275 52T274 28V19Q270 2 255 -10T221 -22Q210 -22 200 -19T179 0T168 40Q168 198 265 368Q285 400 349 489L395 552H302Q128 552 119 546Q113 543 108 522T98 479L95 458V455H55V458Z\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z\" transform\u003d\"translate(500,0)\"\u003e\u003c/path\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M465 605Q428 605 394 614T340 632T319 641Q332 608 332 548Q332 458 293 403T202 347Q145 347 101 402T56 548Q56 637 101 693T202 750Q241 750 272 719Q359 642 464 642Q580 642 650 732Q662 748 668 749Q670 750 673 750Q682 750 688 743T693 726Q178 -47 170 -52Q166 -56 160 -56Q147 -56 142 -45Q137 -36 142 -27Q143 -24 363 304Q469 462 525 546T581 630Q528 605 465 605ZM207 385Q235 385 263 427T292 548Q292 617 267 664T200 712Q193 712 186 709T167 698T147 668T134 615Q132 595 132 548V527Q132 436 165 403Q183 385 203 385H207ZM500 146Q500 234 544 290T647 347Q699 347 737 292T776 146T737 0T646 -56Q590 -56 545 0T500 146ZM651 -18Q679 -18 707 24T736 146Q736 215 711 262T644 309Q637 309 630 306T611 295T591 265T578 212Q577 200 577 146V124Q577 -18 647 -18H651Z\" transform\u003d\"translate(1001,0)\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e of the maximum score.\u003c/li\u003e\n\u003c/ul\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"challenge_output_format\"\u003e\u003cdiv class\u003d\"msB challenge_output_format_title\"\u003e\u003cp\u003e\u003cstrong\u003eOutput Format\u003c/strong\u003e\u003c/p\u003e\u003c/div\u003e\u003cdiv class\u003d\"msB challenge_output_format_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cp\u003eOn a new line for each query, print the number of ways to insert exactly \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-1-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e new lowercase letter into string \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-2-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e such that the length of the longest palindromic subsequence of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-3-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e increases by \u003cem\u003eat least\u003c/em\u003e \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-4-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.211ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 521.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e.\u003c/p\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 1\na\n3 2\naab\n3 0\naba\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n104\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\u003cdiv class\u003d\"challenge_explanation\"\u003e\u003cdiv class\u003d\"msB challenge_explanation_title\"\u003e\u003cp\u003e\u003cstrong\u003eExplanation\u003c/strong\u003e\u003c/p\u003e\u003c/div\u003e\u003cdiv class\u003d\"msB challenge_explanation_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cp\u003eWe perform the following \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-1-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"5.33ex\" height\u003d\"2.509ex\" style\u003d\"vertical-align: -0.671ex;\" viewBox\u003d\"0 -791.3 2295.1 1080.4\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(738,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1794,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e queries:\u003c/p\u003e\n\n\u003col\u003e\n\u003cli\u003e\u003cp\u003eThe length of the longest palindromic subsequence of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-2-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"3.544ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 1525.8 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(747,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e \u003ccode\u003ea\u003c/code\u003e is \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-3-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e. There are two ways to increase this string\u0027s length by \u003cem\u003eat least\u003c/em\u003e \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-4-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"5.472ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 2356.1 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(799,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1855,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e:\u003c/p\u003e\n\n\u003col\u003e\u003cli\u003eInsert an \u003ccode\u003ea\u003c/code\u003e at the start of string \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-5-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, making it \u003ccode\u003eaa\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003eInsert an \u003ccode\u003ea\u003c/code\u003e at the end of string \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-6-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, making it \u003ccode\u003eaa\u003c/code\u003e. \u003c/li\u003e\u003c/ol\u003e\n\n\u003cp\u003eBoth methods result in \u003ccode\u003eaa\u003c/code\u003e, which has a longest palindromic subsequence of length \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-7-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e (which is longer than the original longest palindromic subsequence\u0027s length by \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-8-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"5.472ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 2356.1 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(799,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1855,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e). Because there are two such ways, we print \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-9-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e on a new line.\u003c/p\u003e\u003c/li\u003e\n\u003cli\u003e\u003cp\u003eThe length of the longest palindromic subsequence of \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-10-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"3.544ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 1525.8 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(747,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e \u003ccode\u003eaab\u003c/code\u003e is \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-11-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e. There is one way to increase the length by \u003cem\u003eat least\u003c/em\u003e \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-12-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"5.472ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 2356.1 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(799,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1855,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e:\u003c/p\u003e\n\n\u003col\u003e\u003cli\u003eInsert a \u003ccode\u003eb\u003c/code\u003e at the start of string \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-13-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.09ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 469.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M131 289Q131 321 147 354T203 415T300 442Q362 442 390 415T419 355Q419 323 402 308T364 292Q351 292 340 300T328 326Q328 342 337 354T354 372T367 378Q368 378 368 379Q368 382 361 388T336 399T297 405Q249 405 227 379T204 326Q204 301 223 291T278 274T330 259Q396 230 396 163Q396 135 385 107T352 51T289 7T195 -10Q118 -10 86 19T53 87Q53 126 74 143T118 160Q133 160 146 151T160 120Q160 94 142 76T111 58Q109 57 108 57T107 55Q108 52 115 47T146 34T201 27Q237 27 263 38T301 66T318 97T323 122Q323 150 302 164T254 181T195 196T148 231Q131 256 131 289Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e, making it \u003ccode\u003ebaab\u003c/code\u003e. \u003c/li\u003e\u003c/ol\u003e\n\n\u003cp\u003eWe only have one possible string, \u003ccode\u003ebaab\u003c/code\u003e, and the length of its longest palindromic subsequence is \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-14-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M462 0Q444 3 333 3Q217 3 199 0H190V46H221Q241 46 248 46T265 48T279 53T286 61Q287 63 287 115V165H28V211L179 442Q332 674 334 675Q336 677 355 677H373L379 671V211H471V165H379V114Q379 73 379 66T385 54Q393 47 442 46H471V0H462ZM293 211V545L74 212L183 211H293Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e (which is longer than the original longest palindromic subsequence\u0027s length by \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-15-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"5.472ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 2356.1 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(799,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1855,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e). Because there is one such way, we print \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-16-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.162ex\" height\u003d\"2.176ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -791.3 500.5 936.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e on a new line.\u003c/p\u003e\u003c/li\u003e\n\u003c/ol\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e"}}]}