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