题目内容

塔子哥是一个游戏迷，最近沉迷于一款飞机大战游戏中。在这个游戏中，他需要控制一架飞机发射子弹，来消灭出现在屏幕中的敌人。为了让游戏更加有趣和挑战性，游戏设置了两种不同的发射按键，每个按键都有不同的特殊效果。

在游戏中，按下 $A$ 键，飞机会发射出 $2$ 枚子弹，每个子弹会对命中的敌人造成 $1$ 点固定伤害，但不能作用于同一个敌人。而按下 $B$ 键，飞机会发射出 $1$ 枚子弹，该子弹能够对命中的敌人造成巨额伤害并瞬间将其秒杀。

整个游戏一共有 $T$ 个关卡，每个关卡会在屏幕中同时出现 $N$ 个敌人，这 $N$ 个敌人所能承受的伤害也已经确定。当塔子哥消灭当前关卡的所有敌人后，发射出去多余的子弹会消失，游戏会自动进入下一个关卡。

作为一名游戏高手，塔子哥总是能够操纵子弹命中想要攻击的敌人。但是，他还是很好奇每个关卡自己最少需要按几次发射按键才能将所有敌人全部消灭。他找到了你，希望你能够帮助他解决这个问题。

输入描述

第一行输入一个固定数字 $T$ （ $1\le T \le 1000$ ）表示关卡的总数量， $N$ （ $1\le N\le 200$ ）表示每个关卡出现的敌人数量。

接下来 $T$ 行，每行有 $N$ 个数字 $D_1，D_2，.....,D_N$ （ $1\le D_i \le 200$ ）分别表示这 $N$ 个敌人所能承受的伤害。

输出描述

结果共有 $N$ 行，每行一个数字，分别表示对于这个关卡，最少按几次发射按键就可以将敌人全部消灭。

样例

输入

3 3
1 2 1
2 3 2
1 2 3

输出

2
3
3

样例解释

游戏共有 $3$ 个关卡，每个关卡会出现 $3$ 个敌人。

第一个关卡，先按下 $A$ 键控制子弹消灭第 $1$ 个和第 $3$ 个敌人后，再按下 $B$ 键消灭第二个敌人。所以最少按 $2$ 次。

第二个关卡，按下 $3$ 次 $B$ 键分别消灭这 $3$ 个敌人。

第三个关卡，按下 $3$ 次 $B$ 键分别消灭这 $3$ 个敌人。也可以按 $3$ 次 $A$ 键，敌人剩余承受伤害的变化为： [1, 2, 3] ->[1，1，2]->[1,0,1]->[0，0，0]