Từ xâu nhị phân ~𝑆_0~ = "1" người ta sinh ra các xâu ~𝑆_1~, ~𝑆_2~, … , ~𝑆_𝑛~ trong đó ~𝑆_𝑖~ = ~𝑆_{𝑖−1}~ + ~𝑆_{𝑖−1}~. Ở đây ~𝑆_{𝑖−1}~ là xâu nhị phân tạo thành từ xâu 𝑆𝑖−1 bằng cách đảo hết các bit (bit 1 thành bit 0 và bit 0 thành bit 1).

Ví dụ:

~𝑆_0~ = "1"

~𝑆_1~ = "10"

~𝑆_3~ = "10010110"

~𝑆_4~ = "1001011001101001"

Yêu cầu: Cho số nguyên dương ~𝑛~, hãy xác định trong xâu ~𝑆_𝑛~ có bao nhiêu vị trí có 2 bit liên tiếp bằng nhau (tức là đếm số lần xuất hiện của xâu "00" và "11" trong 𝑆𝑛) Dữ liệu vào:

• Dòng 1 chứa số nguyên dương ~T~ ≤ ~10^5~ là số test
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~𝑛~ ≤ ~10^9~ ứng với một test

Kết quả: Ghi ra ~T~ dòng, mỗi dòng ghi một số nguyên duy nhất là số dư của kết quả tìm được khi chia cho 123456789.

Ví dụ:

Input:

4
1
2
3
4

Output:

0
1
2
5