一天，小楼同学在玩原神时，发现自己打出的伤害数值n中，有着一个个闭合的“圆圈”，如0中带有一个圈，而8带有两个圈。他很好奇，如果把n转化为十六进制数后，又会有多少个“圆圈”呢，现在请你帮助他找出圆圈的数量。
输入包含T组测试数据。
开头是一个正整数T (0<T<10)，为测试数据数量。
每行都会有一个十进制数n（0<=n<=5000000)
输出n在十六进制表达式的情况下，所包含的圆圈数量
0、4、6、9、A、D各有一个圈
8、B中各有两个圈
其他都不带有圈