We are currently in Harry Potter: Deadly Hallow Part 2. Harry Potter and Lord Voldemort are facing each other for their final battle. Lord Voldemort has found some Dark numbers which have high attacking power. These Dark numbers are defined as a number whose number of unique prime factors is a prime number. Lord Voldemort started attacking Harry with these dark numbers one by one. But fortunately, Harry also has some Bright numbers to defend him from every attack. Seeing this, Lord Voldemort started doing range attacks on Harry. In range attacks, Voldemort will select a range of numbers (like [L, R]) and attacks with all the Dark numbers present in that range (all the dark numbers present between L and R inclusively) simultaneously. Lord Voldemort has already fired N ranged attacks on Harry. To save himself, Harry called his beloved friend Hermione for help. After a lot of readings and research, Hermione has finally found a magical formula to get Magical Bright Number to win this fight.
Magical Bright Number (MBN) = 2(DT%100001) + M.
DT = Total Dark numbers in N range attacks = (D1+D2+D3+…+Dn).
Di = Total number of Dark numbers in ith range attack. Ith range attack will be given as [Li, Ri] and Di is equal to the number of dark numbers between Li and Ri, both inclusive.
M = Magical Constant.
Now Harry needs your help to find this Magical Bright Number. In Hogwarts, students are taught only base 2 number system. So, you must print the MBN in base2 number system otherwise Harry will not be able to understand the number. To know more about base2 number system, visit this link: https://en.wikipedia.org/wiki/Binary_number.
Input: -
The first line contains a single integer T denoting T independent test cases.
The first line of each test case contains two space-separated integer N and M denoting the number of range attacks by Voldemort and magical constant respectively.
Next, N lines contain 2 space-separated integers, ith line denoting the range of ith attack i.e. [Li, Ri].
Output: -
Output a single line for each test case containing Magical Bright Number. Output must be in Base2 number system without any leading zeros.
Constraints: -
1 < T < 5
1 < N < 100000
1 < L < R < 100000
0 < M < 1000000
For testcase 1:-
D1 = 0
D2 = 1 {6, prime factor of 6 are 2 and 3. Total unique prime factors = 2 and 2 is prime.}
D3 = 3{Dark numbers = 12(2,3), 14(7,2), 15(3,5)}
D4 = 1 {Dark numbers = 10(2,5)}
DT = 0+1+3+1 = (5)%100001 = 5
MBT = 2^5 + 10 = (42 )10 = (101010)2
For testcase 2:-
DT = 0
MBT = 2^0 + 15 = 16 = (10000)2
