/./,($d[$'+$&]+=$d[$']||1)%=1e9+9for$-x6..9x6;<>;print$d[$_/=1x6],$/for<>