// (((////////////////////////////////////////////////////////////////////////////////////////,/////////////////////////////////////////////////////////(
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((,,((((//(((((((((((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((/(//##(/((*,/((((//(((((((((((((((((((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((/&%%%%%%%%%%%,,,,%(((,,/(((((((((((((((((((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((%%%%%%%%%%%%%(,,,.*/*%*,,((((((((((((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((//%%%%%%%%#%%%%%%%%%%%%%%%%%%/(((%#(((((((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((/((%%%%%%%%*%%%%%%%%#(%%%%%%%%%%%/#&&&&&&@&..**(((((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((/(((%#%%%%%%%//&%%#%%*&&*%%%%#%%(%%%%@&@@&&@&&&&&.,*/*,((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((/&%((%%@%%%%%%/(/%%%%%%%*/%%%%%%%%%/(%%(%%(&&#&&**&&&****/,(((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((@@@&/%/#&%%#%/%/#%%%%%/#%%%%%#%*%%%%((%%/%((,**,**//((,****,,,,((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((@&&&@%%%@&#//(//%%%%%((%%*#(#&&%/##&&&#%***(.,,,,/(,********.,,**,(((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((&(&@&&#%%&&*//*/#%%/#%&%@(. /(,#(%%%(&((*//*(((.,,.,,,,.******.,***.,(((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((/#*%*%#&(./(#*#/,//%@%%%%#(&&&&(#@@/%%(%(*#**///((((((,,************,.***,,((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((*#(/&&%//((((/*/(///(%%(%%&&&&&&@%%%(*##%&/(//(*(((((((,,,.***********,**,,,(((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((/%%%##*((/&&&&&&&&&*/*#%&*%/&&&&((##%&&&/&&/((((((((((((((,,*******,,,,,,,,,,,,((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((%%/&#/*///(&&&&((&&&&**&%(%*/(&&&(%.&(&&&&&@((((((((((((((((*,,,,.,,,,,,,,,,,,.,,((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((%&,////(///,//*/&&&&&&%&&&@*@/@//(&&*&#*. *&&%(.,,,,,,,,,,,/,*//***,.*,,.,,,.,,,,,,,/((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((&*////,////****.*,&&&&&&&&&&&&&&(%//*(/#&&&%&#/,.,,,,,,.,,,.********.**,.,,,,,..,,,,.(((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((#/////*//(%//.**,.***#&&&&%&/(/(/.*,(/.&@@(@**(**./,,,,,,,,,,*******,,,,*,,.,,,,,,,,,,*((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((&/(//////%%%%/%%%**,,**** ((/((/((/.,,.,//*@@@@@%** (/*,(((/.,.*.******,,,,*,,,,,,,,,,,,,((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((/&/((//*/*&%%%%/%%%,,*,,*,*****,*//**.,,,.,,*./*@@@@(....,(**((/(/***.*,****,,.,,,.,,,,,.,,/(((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((%/(((//&/*%%%%%/%%%,***.***,,** .,,,,,,,.,,,..*(*(/@%/(/*/...(%@@(/*(***/*.***,.,,,.,,,,.,,((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((/%#((((/*%#*%%%(%%%%%,***,,,.**,,,***..,,,,,,,.,,((*@@/%%@@@@&&#& .. @@*((**,*,**.,,,.,,,.,,,((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((&&((((((*%%(#%%%%%%%%/****.,,..,,,.,,,.,***,,,,..,./@@@@@%%(/&@@@@@@@( ..,@@/,/*.**,,.,.,,,,,((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((%%((((((/%%%%%%%#%%%%%#****,,...,.*,.,.,,,,,,,...,.,(&@&%&@#(@@&%@@@@@@@&((...(@#,***,,,*((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((((((#%%((((((((%#%%#%%%%%%%%*%,**,.,,,.******.,,.,,,,,,,,,/(@&@@@@%#@@@@@(@@@@@@@@@*....%,**((((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((((/%&((((((((&%/%%%%%&%%%%#/&//**,,*.*******,,*.,,,,,,,,.((((/((((((/&@@&#*@@@@@@&&(* ....,*((((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((/%%/((((((((&%*%%%%%%/%%%*/#////,,,**************,,,,, ((((((/%@&@@@@@@@@&*#%%@/((((*(.... ,*(((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((%%(((((((((&#(%%%%%%/%%%/////////***************,,,,./((((&@@@@@@@@@@@@@,#&%%((%@&(//(( ..  .(((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((&%((((((((((%(%%%%%%%%/&%%///////**************,,.,,,,(((/((@@@@@@@@@&@@@@@&,((*&@@(/(*((/...  ,((((((((((((((((((((((((((((((((((((((((((((
// (((((((((#%/(((((((((/%#%%%%%%%//%%///////*****,*****,,,,****.,,,.(((&&@@@%(#&@@@@@@(((/@@@/((/(*((((..   ./((((((((((((((((((((((((((((((((((((((((((
// ((((((((*%(((((((((((%(#(%%%%#%*/%&/////,**.*******,,*******,,,,,, ((/@@@@@@@@@@@@@@@@@#(*(/((/(/((((..    ..((((((((((((/((((((((((((((((((((((((((((
// ((((((((*(((((((((((/%/(#%%%%/%//*%//////********/*******/,,,,.,,,,,((/(((**/(%@@@@&/##@@@@@@@@(%(((/,.     ,.//*////,((((((((((((((((((((((((((((((((
// (((((((/*((((((((((((%((%%%%%/%////////*****************.,,,,,,,.,,,,,((//((((@@@&/@&&@@&@((*/*(*((((.,     ,,.///((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((%(((&%%%/%*/////,*****,**********,,.,,,,,,,,,.,,,//((@@@@(@@@@@&@&#@&@@@&@#/*(((/,,,   ,,,.*//*/#(((((((((((((((*((((((((((((((((
// (((((((/((((((((((((/%(((/%%//%#////****,***********.,,,,,,,,,,,,,,,.,/(*%@@@@@@@@@@@@@@@@@&@@#((/*((((.,,, ,,,.,/*//%#((,((/(((((/&((((((((((((((((((
// (((((((/(((((((((((((%%(((#%%(/%,******************,,,,,,.,,,,,,,,,,*%@%@@@@@&&@@&@@@@@@@@&@@&&&(/*((((.,,,,,,,.**/*/.#&*(%%%%%/((((((((((((((((((((((
// (((((((*((((((((((((((%%((((,***,****************.,,,,,,,,,,,,,,,,,,(@&//(((/*%@@@@@@@@@/(((@@@#@(.....,,.,,,,,.***////((/%&((((((((((((((((((((((((((
// (((((((#/((((((((((((((#(*******,.**************,,,,,,,,,,.,,,,,,,,#/((/(%@@@@@@@@@@@&(/@@@@@@@@@,,,,,..,,,,,,,.,**,/////*((((((((((((((((((((((((((((
// (((((((/&((((((((((((((((*.,,.,***************.,,,,,,,,,,,,,,,,,,/@@@@@@@@@@@@@@@@@@@@@@@@&&/@@@/.,,,,,.,,,,,,,,*****,*//%%%((((((((((((((((((((((((((
// ((((((((/%((((((((((((((((,******************,,,,,,,,,,,,,,.,,(*@#@&@@@@@@@@@@@@@@@@@@@@@&(@@@&@ ..,,,,,,.,,,,,,,***,/((((*,#%&(((((((((((((((((((((((
// (((((((((((%(((((((((((((.*****************/,/.,,,,,,,,,,,,.(*@@@@&@@@@@&@@@@@@@@@@@@@@*((&@@@@( .,,,,,,,,,,,,..****,.((((((((((#*((((((((((((((((((((
// (((((((((((((((((((((((,****************/*//////.,,,,,,,, (.&&&@@@@@@@@@@@@@@@@@@@@@@(((%@@@@@@@ .,,,,,,,,,,,,*****,,.((((((((((((//((((((((((((((((((
// ((((((((((((((((((((((/****************((((((/***/,,,,,,/(((((%&&@@@@@@@@@@@@@@@@&/((((&@@@@@&#@ ...,,,,,,,,,,****,,.*/(((((((((((((,(((((((((((((((((
// (((((((((((((((((((*************.****((//,(((((((((,,,,,((((((((((@%@@@@@@@@@@@&((((/&@@@@@@@&#@  ,,,,,,,,,,.***,,,,,//#((((((((((((((((((((((((((((((
// (((((((((((((((((/*****************(((((((%#/(((((((((*/(((((((((/..*&%@@@@@@@@@@@@@@@@@@@@@@@%@ .,,,,,,,,,,**.,,,,(,//#((((((((((((((((((((((((((((((
// ((((((((((((((((*****************(((((((((((((((((((((((*(((((((( ..... &@(@@@@@@@@@@@@@@@@@@@%@..,,,,,,,.,*, ,,,,.(((*&&(((((((((((((((((((((((((((((
// (((((((((((((((((**************/(((((((((((((((((((((((((/(((((((........../@@@&#%&@@@@@&@@@@@@@..,,,,.....,,,,,,,,((((/&#((((((((((((((((((((((((((((
// (((((((((((((((((/******/****((((((((((((((((((((((((((((((/((((,,,,,......................... ..,..,,,,,,*,,,,.,,,((((((/((((((((((((((((((((((((((((
// (((((((((((((((((*********((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,.............,..  ........  . ,,,.,,,,*((((((*((((((((((((((((((((((((((((
// ((((((((((((((((((*****(((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,,.,,,......,,,, .......,,,,,,..,,,,,,,((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((*/((((((((((((((((((((((((((((((((((((((((.,,,,,,,,,,,,,,.....,,,,,,,..... ...,,,,,,,,..,,,,,*(((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((*,,,,,,,,,,,,..,,,,,,,,,,. ... ..,,,,,,.,,,,,,****,.,(((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,,,,,,,,,,.,.........,,,,,,,,,,,,*** ...(((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,,,,,,,,,,,,.((......, .,,,,,,,,.*. ....(((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((,,,,...,,,,,,,.,,,,,,,,,,,/((*....,,,,.,,,,,,,,,,,,,,.*((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((.,....,,,,,,,,.,,,.,,,,,,,/(((( ...,,,,,,.,,,,,,,,,.,,.,((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((,...,,,,,,,,,,.,,.,,,,,,,,*((((((....,,,,,,,,,,,,,,,..,..((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((((.,,,,,,,,,,,,...,,,,,,,,,,(((((((/...,,,,,,,,,,,,.,,.,,..((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,..,,,,,,,,,,,(((((((((....,,,,,,,,,,,,..,,,..((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,.,,,,,,,,,,,,((((((((((/....,,,,,,,,,,,,,,..../(((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,,,,,,,,,,,,,.((((((((((((.....,,,,,,,,,,,,,....,(((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,,,,,,,,..,,,,(((((((((((((,.....,,,,,,,,,,,,,....(((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((/,,,,,,,,,,,,,,,,,,,,,,,,,,(((((((((((((((.....,,,,,,,,,........(((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,.,,,.,,,,,,,,((((((((((((((((...,,,,,,,,........,..(((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,.,,.,,,,,,,,.(((((((((((((((((,...,,,,,.......,,,...(((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((((,,,..,,,,,,,,.,,,,,,,,,,,,(((((((((((((((((((/........,,,,,,,,..../((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((((*.,.. ,,,,,,,,,,,,.....(((((((((((((((((((((/.. ..... ..,,,,,,,...((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((.....,,....,,,,,,..... .(((((((((((((((((((((((.,,,, ....... ,,,,. ..*(((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((((,,,. .,,,...............((((((((((((((((((((((((/,,,,,..............*((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((/,,,,, ,,,,,,,..    .....(((((((((((((((((((((((... .,,,,,,............,((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,.,.............((((((((((((((((((((((((.,,,,. ........ ........,(((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,,,,,,......... (((((((((((((((((((((((((/..,,,,,,,,,,....,,, ...*(((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,,,,......... ..((((((((((((((((((((((((((,,,,,,.,,,,,,,,,,..,,,..,(((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((((((,,,,,,,............/(((((((((((((((((((((((((((,,,,,,,,,,,,,,,,,,,,,,(((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((((/&&&/,,,,...... ./((((((((((((((((((((((((((((((((((((/((//,...,,,,,.,(((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((((/&&&&&#/(///((/(*((((((((((((((((((((((((((((((((((((((/((//(/(/(((/((*(((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((*&&&&&&&&///((/((((((((((((((((((((((((((((((((((((((((((&&&&&&%//(//(//(((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&((/(((*((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&/((/((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&&&&(((/(((((((((((((((((((((((((((((((((((((((((/&&&&&&&&&&&%(//((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&&&&&(((((((((((((((((((((((((((((((((((((((((((((*&&&&&&&&&&&&/*((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((#&&&&&&&&&&&&&#(((((((((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&&&(((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((@&&&&&&&&&&&&((((((((((((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&&&/(((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&&&//((((((((((((((((((((((((((((((((((((((((((((((((((@&&&&&&&&&&%(((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&/(/((((((((((((((((((((((((((((((((((((((((((((((((((((%&&&&&&&&&&(((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((&&&&&&&&&&(/((((((((((((((((((((((((((((((((((((((((((((((((((((((((&&&&&&&&&%((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((@&&&&&&&&(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((*&&&&&&&&&((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((((((((&&&&&&&&/(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((&&&&&&&&&(((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((#&&&&&&&(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((%&&&&&&&&(((,,,,,/((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((@&&&&&&&(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((( ,,,&&&&&&&&&,*(#(*.,((((((((((((((((((((((
// (((((((((((((((((((((((((((((((((((((((&&&&&&&/*((((((((((((((((((((((((((((((((((((((((((((((((((((((((((*//.,.@&&&&&(*&&&&&&&@/(((((((((((((((((((((
// ((((((((((((((((((((((((((((((((((//((@&&&&&&%((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((/@&((/*/,*(/*&@&&&&&&(((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((/(&&#(((&&&@/,**(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((%&&&&&&&&&&&&/&&&&((**/((((((((((((((((((((
// (((((((((((((((((((((((((((((((%&#&&&&&@*/&@&&&&%.,(((((((((((((((((((((((((((((((((((((((((((((((((((((((((,@&&&&&&&&&&&&&&,#/ /(,(((((((((((((((((((
// (((((((((((((((((((((((((((((((#@/&&&&&&&&&&&&&%@(*((((((((((((((((((((((((((((((((((((((((((((((((((((((((((&&&&&&@&&&&&&(##*,(#,(@(#/(((((((((((((((
// (((((((((((((((((((((((((((((((/&@(@&&((((/&&@/((/((((((((((((((((((((((((((((((((((((((((((((((((((((((((((&&&&&&&%@&&&&/##*%/&&/#,%#/@/((/*(((((((((
// (((((((((((((((((((((((((((((((%####((((((#@#((#((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((%&@&&&&&&&@*@&&&###&&&&&@#@@&&&&&&@(((((((
// ((((((((((((((((((((((((((((((/*,///.(#(#**/((*/((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((&&&&&&%#&&&&&&&#@((#@&&&&&&(/@&&&@((((((((
// ((((((((((((((((((((((((((((((#&@((#(/#(/,###*//((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((,///(//*//%@(&&&&&&&&&&&&&&%(&&&(((/((((((
// (((((((((((((((((((((((((((((/##,**#/#####,&&&(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((*(////////(//(( (&@@&&&/@@@@&( ,,,,((((((
// (((((((((((((((((((((((((((((/&&*@,######*#*&&((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((*((///////////((*(((((((((
// ((((((((((((((((((((((((((((%&&*(%##(/#/((&&%/((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((%&&(&&&&&&&&&&(&&&#((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((@&(&&&&&&&&&&&(%(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((*&&&&&&&&&&&@&%((((/(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
// (((((((((((((((((((((((((((//,@&&&&&(((((((#.,((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((*/////(*..,,,,,,/(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
// ((((((((((((((((((((((((((((((((/*///,,*((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
#include <bits/stdc++.h>

using namespace std;
template<typename T1, typename T2> inline bool chkmin(T1 &a, T2 b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> inline bool chkmax(T1 &a, T2 b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
const string FILENAME = "input";
const int MAXN = 100228;
const int MAXK = 18;

bool check(string s) {
    int j = 1;
    while (j < sz(s)) {
        if (s[j] >= s[j - 1]) {
            j++;
            continue;
        }
        break;
        j++;
    }
    while (j < sz(s)) {
        if (s[j] > s[j - 1]) {
            return false;
        }
        j++;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        if (check(s)) {
            cout << s << '\n';
            continue;
        }
        int j = 0;
        for (int i = 1; i < sz(s); i++) {
            if (s[i] >= s[i - 1]) {
                j = i;
            } else {
                break;
            }
        }
        if (j == sz(s) - 1) {
            for (int i = sz(s) - 1; i >= 0; i--) {
                if (s[i] != '0') {
                    s[i]--;
                    break;
                }
            }
            cout << s << '\n';
            continue;
        }
        for (int i = 0; i <= j; i++) {
            cout << s[i];
        }
        char ch = '9';
        bool already = false;
        for (int i = j + 1; i < sz(s); i++) {
            if (already == true) {
                cout << ch;
                continue;
            }
            ch = min(ch, s[i]);
            if (s[i] != ch) {
                already = true;
            }
            cout << ch;
        }
        cout << '\n';
    }
    return 0;
}