#!/bin/sed -f
s/^/@/
:a
/@0\?$/{s///;b}
/[02468]$/s/.*@/0&/
/[13579]$/s/.*@/1&/
s/@/&#/
:b
/#1$/{
  s///
  ba
}
/#10/{s//5#/;bb}
/#11/{s//5#1/;bb}
/#12/{s//6#/;bb}
/#13/{s//6#1/;bb}
/#14/{s//7#/;bb}
/#15/{s//7#1/;bb}
/#16/{s//8#/;bb}
/#17/{s//8#1/;bb}
/#18/{s//9#/;bb}
/#19/{s//9#1/;bb}
/#[3579]/{
  h
  s/.*#\(.\)*/\1/
  y/3579/1234/
  G
  /#.$/{s/\(.\)\n\(.*\)#./\2\1/;ba}
  s/\(.\)\n\(.*\)#./\2\1#1/
  bb
}
/#[02468]/{
  h
  s/.*#\(.\).*/\1/
  y/02468/01234/
  G
  s/\(.\)\n\(.*\)#./\2\1#/
}
/#./bb
s/#//
ba