题目描述

多多是一只小菜鸟，都说笨鸟先飞，多多也想来个菜鸟先飞。于是它从 0 点出发，一开始的飞行速度为 1m/s，每过一个单位时间多多的飞行速度比上一个单位时间的飞行速度快 2m/s，问 n（$0 < n < 10^5$）个单位时间之后多多飞了多远？

输入格式

先输入一个整数 T（$1 \le T \le 32767$）表示有几组数据。每组数据输入一个 n，表示多多飞行的时间。

输出格式

输出多多飞行了多远，因为数字很大，所以对 10000 取模。

输入数据 1

2

1

2

输出数据 1

1

4

提示