Little K,who hates math, has got a series1¹+2²+3³+…+nⁿ (1<=n<=1000).He wants to know the last ten digits of the series, please help him.

The first line contains one integer T, indicates the total test cases. Each test case contains one integer n. (1<=n<=1000,T<=20)

Print a number contains ten digits, if the number’s digits are less than ten, you need to print leading zero.