Компания «ВКонтакте» активно использует языки C/C++ для разработки движков. Старший разработчик Вася — большой любитель языка C, ведь только в нем можно полностью раскрыть потенциал Define-Oriented Programming. В языке C директива #define позволяет сделать прямую подстановку куска кода в любое место программы. Например, при исполнении следующего кода значение переменной $v$ будет равно $11$ (в переменную $v$ запишется результат выражения $3 + 4 \cdot 2$).

Недавно Вася написал небольшую программу, которая заполняет массив большой длины. Программа выглядит следующим образом:

К сожалению, его программа не компилируется в силу несовершенства его компьютера, но ему очень интересно знать, какие значения лежали бы в массиве $values$, если бы ему удалось скомпилировать и запустить программу. Помогите ему это узнать.

Input

В первой строке дано одно целое число $n$ ($1 \le n \le 1\,000$) — количество элементов массива, значения которых интересуют Васю.

Следующие $n$ строк содержат $n$ целых чисел $pos_i$ ($0 \le pos_i \le 1\,125\,899\,906\,842\,623$) — позиции, для которых нужно узнать значение в массиве.

Output

Выведите $n$ строк. В $i$-й строке должно содержаться значение элемента массива на позиции $pos_i$.

见题面 Input 部分

见题面 Output 部分

Начало этого массива выглядит следующим образом: