Migrated from Lutece 1389 Protoss imba or not

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Blizzard Entertainment's bestselling real-time strategy game series StarCraft revolves around interstellar affairs in a distant sector of the galaxy, with three species and multiple factions all vying for supremacy in the sector. The playable species of StarCraft include the Terrans, humans exiled from Earth who excel at adapting to any situation; the Zerg, a race of insectoids obsessed with assimilating other races in pursuit of genetic perfection; and the Protoss, a humanoid species with advanced technology and psionic abilities, attempting to preserve their civilization and strict philosophical way of living from the Zerg. Each of these races has a single campaign in each StarCraft real-time strategy game. In addition to these three, various non-playable races have also been part of the lore of the StarCraft series; the most notable of these is the Xel'Naga, a race which features prominently in the fictional histories of the Protoss and Zerg races.

The Protoss are a race in the StarCraft series. They are composed of two societies, the conservative Khalai Protoss and the exiled dark templar. The Protoss are depicted as a physically strong species with access to advanced psionic abilities. The Protoss are considered the most technologically advanced race of the series and are the focus of two episodes within StarCraft and its expansion Brood War, as well as featuring in campaigns in the authorized add-ons Insurrection and Retribution. Protoss strategy in-game is usually built around the quality of units the player controls rather than thequantity. Originating from Aiur, a planet on the fringe of the galaxy, the Protoss are normally shown in the games and the novels of the series as the nemesis of the Zerg.

A Protoss Zealot, as displayed in StarCraft II.

The Kualai Protoss believes that they can promote their power by meditating, and one of the best way to meditate is to observe the secret Natural Numbers. In general, if you are given two non-negatives number $N$ and $K$, you need to count there are how many pairs$( a , b )$ satisfy that $a$ $xor$ $b \geq K$ ,as $0 \leq a < b \leq N$ . Sure, the good templar can solve this problem easily, but can you solve it?

Input

The first line only contains an positive integer $T$ ( $T \leq 2000$ ) , represents there are $T$ test cases.

For each test case:

The first line contains two positive integers $N$ and $K$.$0 \leq N \leq 10^{500} , 0 \leq K \leq 10^{500}$

Output

For each test case, output in one line a positive integer, represents the answer..

The answer may be large. Please output the answer $modulo$ $(772002 + 233)$.

Samples

2
10 0
5 2

55
12

Note

For the second test , there are $12$ pairs satisfy the condition: $(0,2) , (0,3) , (0,4) , (0,5) , (1,2) , (1,3) , (1,4) , (1,5) , (2,4) , (2,5) , (3,4) , (3,5)$

Resources

IEEEXTREME Programming Competition