Arrange the Bricks!

তোমাকে $N$ টি $1 \times 2$ আকারের ইট দেওয়া আছে যা দিয়ে তোমাকে একটি আয়তক্ষেত্র বানাতে হবে। ইট গুলো রোটেট করা যায়, অর্থাৎ একটি $1 \times 2$ ইটকে $1 \times 2$ আকারের অথবা $2 \times 1$ আকারের দুই ভাবেই ব্যবহার করা যায়।
এখন বলতে হবে, তুমি $N$ টি ইট দিয়ে কতগুলো ভিন্ন আকারের আয়তক্ষেত্রে বানাতে পারো? আয়তের মাঝে কোন শূন্য স্থান থাকতে পারবে না, অর্থাৎ, পুরোটিই ইট দিয়ে পূর্ণ থাকতে হবে।

নোটঃ $a \times b$ আর $b \times a$ কে একই আকার ধরতে হবে।

Input

প্রথম লাইনে একটি $T$ দেওয়া হবে যা দিয়ে টেস্টকেস নির্দেশ করে।
এরপরের $T$ লাইনে একটি নাম্বার $N$ দেওয়া থাকবে যা ইটের সংখ্যা নির্দেশ করে।

**30 পয়েন্টের জন্য: **

• $1 \le T \le 1000$
• $1 \le N \le 10000$

**30 পয়েন্টের জন্যঃ **

• $1 \le T \le 100$
• $1 \le N \le 10^{12}$

**40 পয়েন্টের জন্যঃ **

• $1 \le T \le 100$
• $1 \le N \le 10^{14}$

Output

$T$ লাইন প্রিন্ট করতে হবে। প্রতি লাইনে $N$ টি ইটের জন্য উত্তর প্রিন্ট করতে হবে।

Sample

Input	Output
4 1 2 3 4	1 2 2 2
Possible Dimension for 1 bricks are: 1 x 2 Possible Dimension for 2 bricks are: 2 x 2, 4 x 1 Possible Dimension for 3 bricks are: 1 x 6, 2 x 3 Possible DImension for 4 bricks are: 4 x 2, 1 x 8