有些事情，没有所谓“道理”可讲，因为冥冥之中自有天意。
其实AZY是一个大预言家，阴阳自在他心间，与天地周旋。而他预测未来的方式很简单，但十分有效——翻硬币。（也许Kaifu Lee大大也掌握了这种很厉害的预知之术......）
在桌子上从左到右摆上一排硬币，共有n个。一开始，AZY会把它们全部翻到反面，这是预言前所必须的准备。
第一步，他会把所有硬币翻过来，变成正面。
第二步，他会把每两个硬币中的最后一个翻过来。
第三步，他会把每三个硬币中的最后一个翻过来。
......
直到第n步，他会把最后一个（即第n个，也就是n个硬币中的最后一个）也翻过来。
这时，预言就结束了。仍然是正面的硬币个数，指明了未来的方向。
可是AZY知道，其实，再怎么神机妙算，也唯有自己看不穿，也无法改变，那缘来缘去如水，那生死有命在天。
多组测试数据，每组一个数，为硬币的总个数n, 0<=n<=100007
所有操作结束后是正面的硬币个数。
1
31
1给个例子，对于n=3的情况，状态变化如下：
反反反 -> 正正正 -> 正反正 -> 正反反
所以最后正面的个数是1。
水题，take it easy~