題目描述

若我們要找出 1+2+3+...+n 的和，你可以寫一個簡單的程式把它們一個一個的加起來，又或者可以直接使用以下公式：

S_n = ( 1 + n ) * n / 2

這條題目就是這麼的簡單，你要做的正是找出這個數列和。不過，由於 nn 可能會很大，所以你不必找出確實的 S_n 而只要找出 S_n 的最後 9 個位。

輸入格式

每個輸入數據含有多個測試數值，對於每個測試數值你都要找出正確答案才可以取得該測試數據的分數。以下是每個輸入數據的格式。

輸入數據的第一行上有一個正整數 K，它代表本測試數據中有多少個測試點 (1≤n_i≤10⁴⁰ )。

輸出資料應只含有 K 個整數，每個整數獨立放在一行上。這些整數順次代表著 S_ni 的最後 9 個位的數值。這些數值不能以 0 作為第一位數 (除非數值本身為 0)。換言之實際輸出的數值可能少於 9 個位。

2
18
45011

171
13017566

上例要找的和有兩個，

第一個是 1+2+3+...+18=171，

第二個是 1+2+3++...+45011=1013017566 但只取其最後 9 個位且不以 0 為首位，所以答案為 13017566。