@@=1..<>;for(map" $_",<>,@@){map-$$_+($$_=$$$_//$_//_)&&redo,/( \d+)(.*)/;($a,$b)=sort{$n[$a]-$n[$b]||$b-$a}$$1,$$2;$2?$n[$$a=$b]+=$a-$b&&$n[$a]+1:print$$_,$/}