maybe your host change configuration. if by replacing .htaccess you couldn't fix this follow this steps to go back to default permalinks structure:
1. go to: yoursite.com/index.php?qa=login , fill the login form and login as admin, then
2.go to: yoursite.com/index.php?qa=admin&qa_1=general
3. set URL structure to last option(/index.php?qa=123&qa_1=why-do-birds-sing).