URI Online Judge | 1380

Bacilli Population Growth

By Wanderley Guimarães, IME-USP Brazil
Timelimit: 1

Heinrich Hermann Robert Koch was a German doctor who lived from 1843 to 1910 and was famous for having isolated the bacillus that causes tuberculosis. His studies on the disease that caused many deaths until the mid-twentieth century enabled the development of a vaccine that saved millions of lives across the world. Robert Koch was awarded in 1905 with the Nobel Prize of Medicine and is considered one of the fathers of Microbiology.

One of the studies of Koch was connected to the growth rate of the population of bacilli. Koch noted that the bacilli take a moment of time to reach maturity and initiate the cellular division. Thereafter, the bacillus generates at each instant of time a new individual by a split. Thus, if we assume an initial population with only one individual in the next moment we will also have one (it reaches maturity for division), the following we will have 2, at the other 3, so the 5 and so on.

Your task is, given an integer K, determine the last three digits of the bacilli after K time steps, starting from an initial population with an individual.

Input

The input consists of several instances. The first line of input contains an integer T indicating the number of instances.

Each instance consists of a single line containing an integer K (1 ≤ K ≤ 101000000).

Output

For each instance print a line containing the last three digits of the bacilli after K time instants.

Sample Input Sample Output

5
1
4
10
21312
1000000

001
003
055
744
875