众所周知，英雄联盟adc是很重要的，adc是后期团战的核心，可以给予持续输出和后续收割，因此adc总是可以打出高额输出（4000，2800，443），输出的高低可以说是衡量一个adc好坏的重要指标。而在adc界有这这样一个传说，有着这样一个人，在每次对拼中他的adc总能恰到好处的衔接平A甚至有时还能多A一下，因此他的输出总是比一般人多，他就是公认的慈善大师斗地主之王——yyds。
真令人头大20年老黑铁想打职业，他通过各种关系找到了yyds，希望yyds能教他打ad，让他成为比文波还装杯的人。作为adc界的传说，yyds自然不可能那么简单的答应真令人头大，他给了真令人头大n段adc的ob录像，他希望真令人头大能告诉他如果这几场如果是他打的话输出至少能提高多少，如果真令人头大回答对的话表示真令人头大有点悟性他就答应教真令人头大打ad。但是真令人头大是个大黑铁，通过ob他只知道这个adc造成的总伤害，以及这些伤害都是由技能(1)和平A(0)组成，
例如：连续打了三次技能伤害（111），那么他的总伤害是7；先打了一次技能伤害，接了一下平A，又打了两次技能伤害（1011），那么他的总伤害就是11，其他的什么也看不出来，所以他现在只能求助最强王者的你，希望你帮他算出yyds要的答案。
就是说yyds可以改变操作顺序，可以任意改变技能和平a的顺序，并且可以在技能或者平a后进行任意次的平a，但是技能的使用次数是固定的。
第一行，一个数n（1<=n<=1000）表示yyds给真令人头大的录像数量；
接下来n行，每行一个k（1<=k<=2147483647）表示真令人头大计算出的总伤害
对于每个k输出一行yyds至少可以多打的输出
4 5 443 2800 4000
1 2 23 32 hint:第二个样例5（101）是由先打了一次技能伤害，接了一下平A，又打了一次技能伤害，而yyds可能的输出有 6（110），9（1001），10（1010），12（1100），因此至少多打是输出6 - 5 = 1