Xiao A is a true enthusiast of turn-based games. After winning numerous world-class awards in turn-based games, Xiao A suddenly remembered a turn-based game he played in Jiangnan during his childhood.

The rules of the game are as follows: First, a number $F$ is given, and the game system generates $T$ sets of games. Each set of games consists of $N$ piles of stones. Xiao A and his opponent take turns making moves. In each move, the player first chooses a positive integer $M \ge 2$ (the player chooses $M$ themselves, and it can be different for each move), and then splits any pile of stones with a quantity of at least $F$ into $M$ piles, such that the pile with the most stones has at most 1 more stone than the pile with the fewest stones (i.e., they are divided as evenly as possible; in fact, with this method of splitting, the state after splitting is fixed once $M$ and a pile are chosen). When a player cannot make a move, which means when the number of stones in every pile is strictly less than $F$, that player loses. (Note: After the first player chooses a pile with at least $F$ stones from the $N$ piles and splits it into $M$ piles, there are $N+M-1$ piles in total. Then Xiao A chooses a pile with at least $F$ stones from these $N+M-1$ piles, and so on.)

Xiao A has been a gentleman since he was a child, so he invites his opponent to go first. Xiao A now wants to know, given a set of games, and assuming his opponent is as brilliant as he is, who will win?

Input

The first line contains two positive integers $T$ and $F$, representing the number of game sets and the given number, respectively.

The next $T$ lines each describe a game. The first number $N$ in each line represents the number of piles in the initial state of that game. This is followed by $N$ positive integers, representing the number of stones in each of the $N$ piles.

Output

Output a single line containing $T$ numbers (0 or 1) separated by spaces. A 0 indicates that Xiao A (the second player) will win, and a 1 indicates that Xiao A's opponent (the first player) will win.

Constraints

• For 10% of the data: $T=1, N=1, F \le 1$, number of stones in each pile $\le 10$.
• For 20% of the data: $T \le 100, N \le 2, F \le 1$, number of stones in each pile $\le 10$.
• For 30% of the data: $T \le 100, N \le 100, F \le 1$, number of stones in each pile $\le 10$.
• For 40% of the data: $T \le 100, N \le 100, F \le 5$, number of stones in each pile $\le 15$.
• For 70% of the data: $T \le 100, N \le 100, F \le 1000$, number of stones in each pile $\le 1000$.
• For 100% of the data: $T \le 100, N \le 100, F \le 100000$, number of stones in each pile $\le 100000$.
• All numbers above are positive integers.

Examples

Input 1

4 3
1 1
1 2
1 3
1 5

Output 1

0 0 1 1