Alice has a magical mango garden. There are mango trees. the magically -th tree has number of mangoes. Here, represents the number of the divisors of .
Bob wants to buy all the mangoes. Before buying mangoes, Alice offered to Bob that if Bob could answer all the queries correctly, Alice would give the mangoes for free.
Alice will ask queries. Each of them will contain a range . Now, Alice and Bob will play a game. Alice will make the first move. He will choose a tree from the range and collect mangoes from it as many as he wants. Then Bob will do the same. The person who can't collect any mangoes in his turn loses the game. Bob will have to answer who will win if both of them collect mangoes optimally. (At the beginning of each query, magically the number of mangoes in the -th tree will be )
FYI: Bob gets the mangoes for free. Now, you have to say what was Bob’s answer for each query.
The first line contains a integer , the number of queries.
Next lines contain two positive integers , denotes the left and the right ends of the corresponding range.
For each query, print (without quotes) if Bob’s answer was “Alice will win”, otherwise print (without quotes).
3 1 3 2 3 3 9
Alice Bob Alice
Login to submit
Prerequisite: Nim Game (Game Theory), Divisor Sieve (Number Theory) Explanation: At first, we have t...