Vượt qua hành lang ánh sáng, nhóm thám hiểm cuối cùng cũng bước vào Đại Sảnh Đường, nơi ngai vàng của vua KDA ngự trị.

Không gian ở đây đặc quánh lại, không khí rung lên bần bật theo từng đợt sóng vô hình. Ở giữa sảnh, lơ lửng ngay trên ngai vàng, là một khối tinh thể khổng lồ đang đập từng nhịp thong thả nhưng nặng nề. Đó là "Trái Tim Hổ Phách" - nguồn năng lượng duy trì sự "bất tử" cho cả vương quốc này.

Nhà hiền triết nhận ra rằng, để phá giải lời nguyền, họ không thể đập vỡ trái tim (vì sẽ khiến cả vương quốc sụp đổ), mà phải hòa nhịp với nó để tháo gỡ các phong ấn thời gian.

Trái tim này hoạt động theo một quy luật dao động năng lượng cổ xưa gọi là "Tam Giác Hư Không":

• Nhịp đập đầu tiên phát ra mức năng lượng là ~a~.
• Nhịp đập thứ hai phát ra mức năng lượng là ~b~.
• Từ nhịp đập thứ 3 trở đi, mức năng lượng sinh ra là sự giao thoa (phép XOR) của hai nhịp đập ngay trước nó.

Nói cách khác, nếu gọi ~F[i]~ là mức năng lượng tại nhịp thứ ~i~, ta có:

~ \begin{align} F[1] &= a \\ F[2] &= b \\ F[3] &= a \oplus b \end{align} ~

Để thực hiện nghi thức giải nguyền tại một thời điểm ~N~ (tức là tại nhịp đập thứ ~N~), các bạn cần phải biết được tính "ổn định" của dòng năng lượng đó. Cụ thể, các bạn cần đếm xem trong quá khứ, từ nhịp đầu tiên cho đến nhịp hiện tại (từ ~1~ đến ~N~), đã có bao nhiêu lần mức năng lượng giống hệt với mức năng lượng tại thời điểm ~N~ xuất hiện.

Vì "Trái Tim Hổ Phách" đã đập từ hàng ngàn năm nay, số ~N~ có thể vô cùng lớn. Hãy giúp nhà hiền triết trả lời các truy vấn này thật nhanh chóng.

Input

Dòng đầu tiên chứa 3 số nguyên ~a~, ~b~ là hai mức năng lượng khởi đầu và ~T~ là số lần cần kiểm tra (~0 < a, b \le 10^{18}, 1 \le T \le 10^5~). ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~N~ (~1 \le N \le 10^{18}~).

Output

In ra ~T~ dòng, mỗi dòng là một số nguyên duy nhất là số lượng vị trí ~i~ (~1 \le i \le N~) sao cho ~F[i] = F[N]~.

3 4 2
1
4

1
2