Skyler White and Marie Schrader usually go for shopping in the night every other week in Albuquerque.

One night they were out shopping somewhere near Los Pollos Hermanos. Marie had her eyes on the jewelry section of the shop. But, Skyler warned her not to shoplift here because of the consequences they faced earlier in Breaking Code 1.0

Last time they encountered a problem using binary strings, but this time they have a different problem.

Skyler told Marie that she got to know about some interesting numbers, called Palindromic Numbers last night

Since they are always up for discounts in expensive products and coupons offered, the shop owner put up an interesting way to offer discounts.

They got to see a strange riddle in the front of the shop. Whoever solved that riddle, they got a huge discount in the jewelry section. Since Skyler refused to shoplift with Marie, they both need to solve the puzzle in order to get Marie some expensive products.

The puzzle stated -

"For a given N, find out sum of all distinct N-digit Palindromic Numbers"

There are many values of N given in the shop. Please help them so that they can buy some expensive gifts for them!

INPUT

• First line contains an integer T, the number of Test Cases.
• Each test case consists of a single line, denoting N.

OUTPUT

• Output the answer of each test case in a separate line. Since the answer could be very large, output it modulo 10⁹+7.

CONSTRAINTS

• 1 ≤ T ≤ 10⁵
• 1 ≤ N ≤ 10⁹