One fine day Walter White was busy making some special compounds in his lab. These compounds have some special properties. These are straight chain compounds consisting of only 2 types of elements '0' and '1'. Also elements to same type cannot share a bond. So some of the compounds are named as '1' , '101' , '0'.

Now he assigns a secret key to each element. Secret key is simply the decimal representation of the compound name(eg. secret key for compound '101' is 5). These compounds are to be stored in different storage containers numbered from 1 to infinity (1,2,3,4,......) in increasing order of their secret key (i.e compound with secret key 0 is stored in container 1, compound with secret key 1 is stored in container 2 .... so on ).

Walter White needs your help for storing the compounds. You are given the container number n and you have to tell him the secret key of the compound corresponding to that container. Since the secret key can be very large output it modulo 1000000007.

INPUT

The first line contains an integer T denoting the number of test cases.
T test cases follows each containing a single integer n.

OUTPUT

For each test case output the answer to the question in separate line.

CONSTRAINTS

1<=T<=10^5
1<=n<=10^9