Q.E.D. is a detective manga, created and produced by Motohiro Katou. Sou Touma is a university graduate who encounters a variety of investigative cases after returning to Japan from the US. He works with his friend, Kana Mizuhara, combining his deductive skills with Mizuhara’s social gifts.

Sou Touma is the main character of the series. Though he is a genius detective, he is not particularly interested in going out and finding wrongs to right. Rather, it is his erstwhile partner Kana who drags him into getting involved. An introvert, he is well-known for his intelligence, although he is not particularly popular.

The most interesting part of the story is that you read the story in Touma’s perspective. You can enjoy deducing with Touma without the spoiler. Touma majors in math so that he will use math induction to make the deduction. It’s a good manga for STEM students.

One day, Touma receives an anonymous letter with the following question: Given two positive integers a and b.

Count the number of pairs (i,j) such that i & j = 0. (i bitwise-and j = 0), ∀0 ≤ i ≤ a,∀0 ≤ j ≤ b. Could you solve it for Touma? 

The first line contains an integer T (T ≤ 10000), which indicates the number of test cases. For each case, one line contains two space-separated integers a, b (1 ≤ a, b ≤ 10^9).