Description

第二个任务是：僵尸生存游戏。

一只僵尸邪魔徒会每隔

分钟就袭击一个人类，被袭击的人类在被袭击的

分钟后就会被转化成僵尸邪魔徒。 ​ 最初只有一只僵尸邪魔徒，请问在第 分钟结束的时候，会存在几只僵尸邪魔徒？

注：字幕来源 KRL 字幕组。

Input Format

第一行一个整数 ，表示测试数据组数。 接下来是 组测试数据。 每组测试数据共一行，包含一个整数 。

由于答案可能很大，所以只需要输出其对 取模的结果即可。

注：取模的结果即这个数字在除 时得到的余数，例如 对 取模的结果为 ，因为 除 商为 余数为 。

Output Format

对于每组测试数据，输出一行一个整数，表示在第

分钟结束的时候，会存在几只僵尸邪魔徒。

4
1
5
7
100​

1
2
3
987228961​

Hint

在第 分钟结束时，最初的僵尸邪魔徒袭击了第一个人类。

在第 分钟结束时，最初的僵尸邪魔徒袭击了第二个人类。

在第 分钟结束时，被袭击的第一个人类转化成了第二只僵尸邪魔徒。

在第 分钟结束时，最初的僵尸邪魔徒袭击了第三个人类。

在第 分钟结束时，被袭击的第二个人类转化成了第三只僵尸邪魔徒，第二只僵尸邪魔徒袭击了第四个人类。

所以在第 分钟结束后，总共有两只僵尸邪魔徒，在第 分钟结束后，总共有三只僵尸邪魔徒。