//,map$%+=($#{$'}=$#{$'>>1}+$'%2)==$#$_&&$'&$_,@@for@@=1..<>;print$%