Turjo and Urjo are two exceptionally good brothers. One lazy Friday afternoon, the power went out, leaving them completely bored with nothing to do. To pass the time, Urjo decided to invent a math game to challenge Turjo's calculating speed.

Urjo grabs a piece of paper and writes down two starting numbers, $$$A$$$ and $$$B$$$. He then tells Turjo that he is generating a special sequence. However, since standard addition is way too easy for them, Urjo uses the Bitwise XOR operator ($$$\oplus$$$) to generate the next terms.

Let $$$F$$$ be a sequence. The sequence is defined by Urjo as follows:

$$$$$$F_{1} = A$$$$$$ $$$$$$F_{2} = B$$$$$$ $$$$$$F_{i} = F_{i-1} \oplus F_{i-2} \ for \ all \ i \ge 3$$$$$$

The rules of the game are simple: Urjo will suddenly shout a number $$$N$$$. In order to win the game and prove he is the superior brother, Turjo must instantly shout back the exact value of the $$$N^{th}$$$ term in the sequence defined as $$$F_{N}$$$.

He needs your help to write a lightning-fast program so he can beat his brother and win the game!

Constraints

• $$$1 \le N \le 10^{18}$$$
• $$$0 \le A, B \le 10^{18}$$$

The group chat was once buzzing with messages, reactions, memes and jokes every second just like the peak of every group chat. Alas, the glory days are now over, only Aritro sends messages in the chat now. The others have a life now!

There are $$$N$$$ inactive friends in the chat. Aritro sends messages one by one, and each message is assigned an id equal to the number of messages sent so far, including this message. So his first message has id $$$1$$$, his second has id $$$2$$$, and so on.

A friend can come online at any point. When friend $$$f$$$ comes online, he reads all messages that have been sent so far, and then immediately goes offline. If Aritro sends more messages after that, friend $$$f$$$ will not see them unless he comes online again.

You will be given events in order. Each event is one of the following:

• Aritro sends a message. It is assigned the next available id.
• Friend $$$f$$$ comes online and reads all messages sent so far. He then goes offline.
• How many friends have read message with id $$$s$$$.

Note: A friend reads message $$$s$$$ if and only if he came online at a time when at least $$$s$$$ messages had already been sent.

Constraints

• $$$1 \le N \le 5 \times 10^5$$$
• $$$1 \le Q \le 5 \times 10^5$$$

Through the dark forests, crossing seven seas and thirteen rivers, Pepe has finally reached the mythical Island of Bika. There he found a cave. Some old saying says that whoever finds a cave on the Island of Bika and enters it never comes back alive, but Pepe is known as the most courageous in his village. So, he decides to enter it. There he finds a locked chest and a note beside it. The entrance immediately closes but fortunately Pepe had come with a torch. Pepe starts reading the note:

You are given two positive integers $$$n$$$ and $$$x$$$. There is an array $$$a$$$ consisting of $$$m$$$ non-negative integers. Let $$$m$$$ be the size of the array $$$a$$$. For each $$$i$$$ ($$$1 \le i \le m$$$), $$$a_i$$$ is the base of the $$$i$$$-th summand, and $$$x$$$ is the common exponent of every summand.

Formally,

$$$$$$n = a_1^x + a_2^x + \dots + a_m^x$$$$$$

Your task is to find the minimum possible value of $$$m$$$, i.e. the minimum possible size of $$$a$$$.

Pepe has to enter the answer and the array $$$a$$$ into the chest, which contains a smart lock system. It is said that the Island of Bika was once the greatest in technology.

Help Pepe get the treasure and escape the cave.

Constraints

• $$$1 \le T \le 1000$$$
• $$$1 \le n \le 10^5$$$
• $$$1 \le x \le 10$$$

Subtasks

• If you choose not to print the sequence of numbers for any test case but provide the correct answer $$$m$$$, you will receive $$$50\%$$$ of the subtask's score
• If you choose to print the sequence, but it is incorrect, you will receive $$$0$$$ points for that subtask.
• Otherwise, you will receive full score for the subtask.