Şimal-şərq kralı Hard#3175
Aşağı sol küncdə n \times n ölçülü kvadrat şahmat taxtasında bir şah yerləşib. Şah yalnız bir xana sağa, bir xana yuxarı, və ya bir xana sağ-yuxarı hərəkət edə bilər. Şahın taxtanın yuxarı sağ küncünə çatmasının müxtəlif yollarının sayını -ə görə qalığı ilə hesablayın.
Birinci sətirdə tam ədəd (1 \leq T \leq 10000) — testlərin sayı verilir. Sonrakı sətirin hər birində bir tam ədəd (1 \leq n \leq 10^6) verilir.
Hər test üçün bir tam ədəd — məsələnin cavabını çap edin.
Nümunə 1