This page is still under construction.

Parts of this page are still being built. What you see may change.

Boundary

Time limit2sMemory limit2048 MB

Summary
For a w by l rectangle, find every a such that the 1-wide boundary ring can be tiled by 1 by a tiles, listing them in order.
Level

Medium6 of 10

Topics
Math, Number theory, Implementation
Solved
No attempts yet

Problem

Bethany would like to tile her bathroom. The bathroom has width ww centimeters and length ll centimeters. If Bethany uses only basic 1×11 \times 1 centimeter tiles, she needs w⋅lw \cdot l of them.

She has something else in mind.

  • On the interior of the floor, she uses 1×11 \times 1 tiles. She needs exactly (w−2)⋅(l−2)(w - 2) \cdot (l - 2) of these.
  • On the floor boundary, she uses tiles of size 1×a1 \times a for some positive integer aa. The tiles can also be rotated by 9090 degrees.

For which values of aa can Bethany tile the bathroom floor as described? Note that aa can also be 11.

Input

Each test contains multiple test cases. The first line contains an integer tt (1≤t≤1001 \le t \le 100), the number of test cases. Each of the following tt lines contains two integers ww and ll (3≤w,l≤1093 \le w, l \le 10^9), the dimensions of the bathroom.

Output

For each test case, print an integer kk (0≤k0 \le k), the number of valid values of aa, followed by the kk valid values a1,a2,…,aka_1, a_2, \dots, a_k in increasing order. It is guaranteed that under the problem constraints, the output contains at most 200 000200\,000 integers.

Examples1

  1. Example 1

    Input
    3
    3 5
    12 12
    314159265 358979323
    
    Expected output
    3 1 2 3
    3 1 2 11
    2 1 2